UVa 11838 Come and Go

題意：
    題目求這個城市是否為一個強連通的城市(從任意點出發可以抵達每個點)，第一行會給N個點和M條路，底下M行每行有V,W,P，如果P==1表示該條路為單向V->W，P==2則是雙向V<->W。

想法：
    SCC模板，檢查scc_cnt是否為1，因為scc_cnt==1表示整個graph都可連通。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector<int> edge[2005];
	int dfn[2005], low[2005];
	int dfs_clock;
	vector<int> Stack;
	int scc_cnt;
	void Tarjan(int cur)
	{
	dfn[cur] = low[cur] = ++dfs_clock;
	Stack.push_back(cur);
	for (int nxt : edge[cur]) {
	if (!dfn[nxt]) {
	Tarjan(nxt);
	low[cur] = min(low[cur], low[nxt]);
	}
	else if (find(Stack.begin(), Stack.end(), nxt) != Stack.end()) // if in Stack
	low[cur] = min(low[cur], dfn[nxt]);
	}
	if (dfn[cur] == low[cur]) {
	++scc_cnt;
	int nxt;
	do {
	nxt = Stack.back();
	Stack.pop_back();
	} while (cur != nxt);
	}
	}
	int main()
	{
	int N, M;
	while (scanf("%d %d", &N, &M) && (N || M)) {
	// Initial
	for (auto &v : edge) v.clear();
	fill(dfn, dfn+N+1, 0);
	fill(low, low+N+1, 0);
	dfs_clock = 0;
	Stack.clear();
	// Input
	int V, W, P;
	for (int i = 0; i < M; ++i) {
	scanf("%d %d %d", &V, &W, &P);
	edge[V].push_back(W);
	if (P == 2) edge[W].push_back(V);
	}
	// SCC: Tarjan Algorihtm
	scc_cnt = 0;
	for (int i = 1; i <= N; ++i)
	if (!dfn[i] && scc_cnt <= 1) Tarjan(i);
	if (scc_cnt == 1) puts("1");
	else puts("0");
	}
	}

view raw [UVa] 11838 Come and Go.cpp hosted with ❤ by GitHub