# 題目: UVa 11838 - Come and Go

# 題目說明

一座城市以單向道及雙向道連接各處
你需要寫一個程式來判斷任意地點是否都能通往任意地點

---

INPUT:
每筆測資的第一行有兩個整數N及M，N代表交叉路口(點)的數量，M代表街道(邊)的數量
接下來會有M行，每行有三個整數V、W和P，代表V及W間有一條道路相連，P代表單向道或雙向道
當N及M皆為零時結束程式

---

OUTPUT:
輸出這個城市是否符合SCC，true則1，false則0

# 解題方法

基本上跟前幾題一樣，也是SCC模板題
只要找出每個城市是否有多於一個SCC即可

# 參考程式碼

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector< vector<int> > G;
vector<int> dfn, low;
set<int> S;
int dep, cnt;

void dfs(int u)
{
	low[u] = dfn[u] = ++dep;
	S.emplace(u);

	for (auto& v : G[u])
	{
		if (!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
		else if (S.count(v)) low[u] = min(low[u], dfn[v]);
	}

	if (dfn[u] == low[u]) S.clear(), ++cnt;
}

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M;
	while (cin >> N >> M, N && M)
	{
		// init
		G.assign(N + 1, vector<int>());
		low.assign(N + 1, 0);
		dfn.assign(N + 1, 0);
		S.clear();
		dep = cnt = 0;

		// store data
		int V, W, P;
		while (M--)
		{
			cin >> V >> W >> P;
			G[V].emplace_back(W);
			if (P == 2) G[W].emplace_back(V);
		}

		// find scc
		for (int u = 1; u <= N; ++u) if (!dfn[u] && cnt < 2) dfs(u);

		cout << (cnt == 1) << "\n";
	}

	return 0;
}

# 參考文章:

https://www.larrysprognotes.com/UVa%20-%2011838/