首頁 Uva Problems

# 題目: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 所連接

# 參考程式碼 - 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/