# 題目:UVa 11504 - Dominos

# 題目說明

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

---

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

---

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

# 解題方法

• 解法一使用Tarjan's Algorithm找SCC(Strongly Connected Component)，當我們推動任何一個點，整個SCC中的骨牌都會倒下
  接著找每個SCC有沒有被其他SCC連接，連接數為零的SCC數量即為答案

• 解法二使用Kosaraju's Algorithm找SCC進行處理，可視為以下：先找出數個連接在一起的tree，將tree root存起來
  接著再反向搜尋這些tree root有沒有被其他tree所連接

# 參考程式碼 - 1

#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;
}

# 參考程式碼 - 2

#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/