# 題目:UVa 247 - Calling Circles

# 題目說明

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

---

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

---

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

# 解題方法

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

先建表，之後進行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/