# 題目: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) 的問題
SCC 強連通分量,指圖上任意兩點 a
及 b
, a
有路徑走到 b
, b
也有路徑走到 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/