例题11-4 电话圈（Calling Circles, ACM/ICPC World Finals 1996, UVa247)

本文主要是介绍例题11-4 电话圈（Calling Circles, ACM/ICPC World Finals 1996, UVa247)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-247
分类：图论
备注：Floyd传递闭包

注意：逗号后面有空格，否则显示WA

代码如下：

#include<iostream>
#include<map>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 30;
string name[maxn];
int n, m, fa[maxn], kase;
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main(void) {while (~scanf("%d %d", &n, &m) && n) {map<string, int>id;bool g[maxn][maxn] = { 0 };int cnt = 0;for (int i = 0; i < n; i++)fa[i] = i;while (m--) {string u, v;cin >> u >> v;if (!id.count(u)) {id[u] = cnt; name[cnt++] = u;}if (!id.count(v)) {id[v] = cnt; name[cnt++] = v;}g[id[u]][id[v]] = true;}for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) if (g[i][k]) for (int j = 0; j < n; j++)g[i][j] = g[i][j] || (g[i][k] && g[k][j]);vector<string>ans[maxn];for (int i = 0; i < n - 1; i++)for (int j = i + 1; j < n; j++)if (g[i][j] && g[j][i] && find(i) != find(j)) {fa[find(j)] = find(i);}for (int i = 0; i < n; i++) {ans[find(i)].push_back(name[i]);}if (kase)cout << "\n";printf("Calling circles for data set %d:\n", ++kase);for (int i = 0; i < maxn; i++) {for (int j = 0; j < ans[i].size(); j++)cout << ans[i][j] << (j == ans[i].size() - 1 ? "\n" : ", ");}}return 0;
}