# 題目:UVa 247 - Calling Circles

# 題目說明

電信公司有一種名為朋友圈的服務,由你提供一組名單,當你打電話給名單上的朋友時,你會獲得折扣
LibertyBell Phone Co 是一間新的電信公司,它們認為它們可以讓其他公司倒閉
LibertyBell Phone Co 也有朋友圈的服務,相較其他電信公司,它們會根據你打給誰和誰打給你判斷出你的朋友圈
例如: A 打給 B、B 打給 C、C 打給 A,那 ABC 是一組朋友圈


INPUT:
每筆測資的第一行有兩個整數 nmn 代表人數, m 代表通話
接下來會有 m 行,每行有兩個字串,代表前者打電話給後者
nm 皆為 0 時結束


OUTPUT:
先輸出是第幾個 set
接著印出每個朋友圈裡所有人的姓名
(姓名以空格分隔、呼叫圈以換行分隔)

輸出姓名的順序不影響結果

# 解題方法

這題是 SCC (Strongly Connected Component) 的問題

SCC 強連通分量,指圖上任意兩點 aba 有路徑走到 bb 也有路徑走到 a

先建表,之後進行 dfs,找到一個朋友圈即輸出

# 參考程式碼

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;
map<string, vector<string>> G;
map<string, int> dfn, low;
vector<string> V;
int dep;
void dfs(string 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], low[v]);
        else if (count(V.begin(), V.end(), v)) low[u] = min(low[u], dfn[v]);
    
    if (dfn[u] == low[u])
    {
        string temp;
        while (1)
        {
            temp = V[V.size() - 1];
            V.pop_back();
            cout << temp;
            if (temp != u) cout << ", ";
            else break;
        }
        cout << "\n";
    }
}
int main()
{
    // fast io
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, cases = 0;
    while (cin >> n >> m, n && m) 
    {
        // init
        G.clear(), dfn.clear(), low.clear(), V.clear();
        dep = 0;
        // store data
        while (m--)
        {
            string name, to;
            cin >> name >> to;
            G[name].emplace_back(to);
        }
        // find scc
        if (cases) cout << "\n";
        cout << "Calling circles for data set " << ++cases << ":\n";
        for (auto& [i, j] : G) if (!dfn[i]) dfs(i);	
    }
    return 0;
}

# 參考文章:

https://www.larrysprognotes.com/UVa%20-%20247/