題目： UVa - 11838 - Come and Go

題目說明

給有向圖，求整張圖是否為一個 SCC ( Strongly Connected Component )。SCC 即在有向圖上任意選兩點 u、v，u 能夠走到 v 且 v 也能夠走到 u。

Input： 每組測資第一行為兩個整數 N、M，分別代表 點的數量 (1 ~ N) 及 邊的關係，若 N、M 都為 0 則結束。接下來 M 行每行有三個整數 u、v、P，若 P 為 1 表示有 u -> v 的邊，若 P 為 2 表示有 u -> v 及 v -> u 的邊。

Output： 若整張圖為一個 SCC 則輸出 1，否則輸出 0。

解題思路

DFS 找 SCC 並紀錄 SCC 的個數即可。需要注意的是當我們知道 SCC 的個數大於一就可以直接輸出了不用繼續往下做。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <stack>

using namespace std;

// reference: https://ppt.cc/fkxbXx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int TIME;
int cnt;
vector<int> dfn;
vector<int> low;
unordered_set<int> inStack;
vector<vector<int>> G;
stack<int> s;

void dfs(int u)
{
    dfn[u] = low[u] = ++TIME;
    s.push(u);
    inStack.insert(u);

    for (auto& v : G[u])
    {
        if (dfn[v])
        {
            if (inStack.count(v)) low[u] = min(dfn[v], low[u]);
            continue;
        }

        dfs(v);
        low[u] = min(low[v], low[u]);
    }

    if (dfn[u] == low[u])
    {
        int tmp;
        do
        {
            tmp = s.top();
            s.pop();
            inStack.erase(tmp);
        } while (tmp != u);
        ++cnt;
    }
}

int main()
{
    int N, M;
    while (cin >> N >> M && !(!N && !M))
    {
        // init
        TIME = 0;
        cnt = 0;
        dfn.assign(N + 1, 0);
        low.assign(N + 1, 0);
        inStack.clear();
        G.assign(N + 1, vector<int>());
        while (!s.empty()) s.pop();

        while (M--)
        {
            int u, v, P; // P 為 1 代表單向 u -> v，為 2 代表雙向 u -> v, v -> u
            cin >> u >> v >> P;

            G[u].push_back(v);
            if (P == 2) G[v].push_back(u);
        }

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

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

參考資料

Programming學習筆記: UVa 11838 Come and Go