# 題目:UVa 11504 - Dominos

# 題目說明

你的目標是找出一個骨牌需要推多少次才會全倒

INPUT:
第一行輸入一個整數 t ，代表有 t 筆測資
每筆測資的第一行有兩個整數 n 及 m ， n 代表骨牌數， m 代表骨牌的連動
接下來會有 m 行，每行有兩個整數 x 和 y ，代表骨牌 x 的倒下會影響骨牌 y

OUTPUT:
輸出要使所有骨牌倒下，需要推動幾個骨牌

點這裡有關 Tarjan's Algorithm 與 Kosaraju's Algorithm 的詳細說明

解法一使用 Tarjan's Algorithm 找 SCC(Strongly Connected Component) ，當我們推動任何一個點，整個 SCC 中的骨牌都會倒下
接著找每個 SCC 有沒有被其他 SCC 連接，連接數為零的 SCC 數量即為答案
解法二使用 Kosaraju's Algorithm 找 SCC 進行處理，可視為以下：先找出數個連接在一起的 tree，將 tree root 存起來
接著再反向搜尋這些 tree root 有沒有被其他 tree 所連接

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

	using namespace std;

	vector< vector<int> > G;
	vector<int> low, dfn, V, com;
	int dep, cnt;

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

	for (auto& v : G[u])
	if (!dfn[v]) dfs(v), low[u] = min(low[u], dfn[v]);
	else if (count(V.begin(), V.end(), v)) low[u] = min(low[u], dfn[v]);

	if (low[u] == dfn[u])
	{
	int temp;
	do
	{
	temp = V[V.size() - 1];
	V.pop_back();
	com[temp] = cnt;
	} while (temp != u);
	++cnt;
	}
	}

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

	int t, n, m, x, y;
	cin >> t;

	while (t--)
	{
	// init
	cin >> n >> m;
	G.assign(n + 1, vector<int>());
	low.assign(n + 1, 0);
	dfn.assign(n + 1, 0);
	com.assign(n + 1, 0);
	V.clear();
	dep = cnt = 0;

	// store data
	while (m--)
	{
	cin >> x >> y;
	G[x].emplace_back(y);
	}

	// find scc
	for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs(i);

	// get result
	int result = 0;
	vector<int> conxt(cnt);

	for (int i = 1; i <= n; ++i) for (auto& j : G[i])
	if (com[i] != com[j]) ++conxt[com[j]];
	for (auto& i : conxt) if (!i) ++result;
	if (!result) ++result;

	cout << result << "\n";
	}

	return 0;
	}

	#include <iostream>
	#include <vector>

	using namespace std;

	vector< vector<int> > G;
	vector<bool> dfn;
	vector<int> V;

	void dfs(int u)
	{
	dfn[u] = true;
	for (auto& v : G[u]) if (!dfn[v]) dfs(v);
	}

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

	int t, n, m, x, y, result;
	cin >> t;

	while (t--)
	{
	cin >> n >> m;
	G.assign(n + 1, vector<int>());
	dfn.assign(n + 1, false);
	V.clear();
	result = 0;

	while (m--) cin >> x >> y, G[x].emplace_back(y);

	for (int u = 1; u <= n; ++u) if (!dfn[u])
	dfs(u), V.emplace_back(u);

	dfn.assign(n + 1, false);
	for (int u = V.size() - 1; u >= 0; --u) if (!dfn[V[u]])
	dfs(V[u]), ++result;

	cout << result << "\n";
	}

	return 0;
	}

感謝 瑋倫 修正解法二的解題說明
http://web.ntnu.edu.tw/~algo/Component.html#8
https://www.larrysprognotes.com/UVa-11504/