題目： UVa - 247 - Calling Circles

題目說明

有一家電信公司記錄了所有人之間打電話的紀錄，他們想找出所有的通話圈圈 ( Calling Circles )
舉例來說，如果 A 打給 B，B 打給 C，C 又打給 A，A、B、C之間就可以跟任何一個人互相溝通，他們就形成一個 Calling Circle。但假如 D 可以打給 A，但 A 不能打給 D，D 跟 A 就不算 Calling Circle。

Input： 每筆測資先給你總共的人數 n，和通話紀錄 m 筆，接下來 m 行會有兩個人名 ( 25字元以內 )，代表前面的人可以打給後面的人 ( 單向 )。

Output： 每筆測資先輸出一行 “Calling circles for data set x:” ( x 代表第幾筆 )，接下來每行輸出一個 Calling Circle 中的所有人名，之間以逗號和空白隔開，順序都可以。

引用自：愚人隨筆: UVA 247 - Calling Circles

解題思路

題目的 Calling Circles 其實就是 SCC ( Strongly Connected Component )，SCC 即在有向圖上任意選兩點 u、v，u 能夠走到 v 且 v 也能夠走到 u。所以我們只需要讀取測資並建圖，之後 DFS 找 SCC 並直接輸出即可。比較特別的是因為名字是字串，所以使用 Map 建圖。

參考解法

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
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <functional>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <string>
#include <stack>
#include <map>

using namespace std;

/*
reference:
想法: https://ppt.cc/fc2nLx
Code: https://ppt.cc/fOJQux
*/

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

int main()
{
    int n, m, Case = 0;
    int TIME;
    stack<string> s;
    map<string, int> dfn;
    map<string, int> low;
    unordered_set<string> inStack; // 紀錄目前存在 Stack 中的點
    map<string, vector<string>> G;

    // 找出 strong connected component
    function<void(string)> dfs = [&](string 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])
        {
            string tmp;
            while (true)
            {
                tmp = s.top();
                s.pop();
                inStack.erase(tmp);

                cout << tmp;
                if (tmp != u) cout << ", ";
                else break;
            }
            cout << '\n';
        }
    };

    while (cin >> n >> m && !(!n && !m))
    {
        // init
        TIME = 0;
        while (!s.empty()) s.pop();
        dfn.clear();
        low.clear();
        G.clear();
        inStack.clear();

        for (int i = 0; i < m; ++i)
        {
            string u, v;

            cin >> u >> v;
            G[u].push_back(v);
        }

        if (Case) cout << '\n';
        cout << "Calling circles for data set " << ++Case << ":\n";
        for (auto& [u, __] : G) if (!dfn[u]) dfs(u);
    }
}

參考資料

愚人隨筆: UVA 247 - Calling Circles
Programming學習筆記: UVa 247 Calling Circles