题目链接:https://vjudge.net/problem/UVA-247
题意:
如果两个人相互打电话(直接或间接),则说他们在同一个电话圈里。例如,a打给
b,b打给c,c打给d,d打给a,则这4个人在同一个圈里;如果e打给f但f不打给e,则不能推
出e和f在同一个电话圈里。输入n(n≤25)个人的m次电话,找出所有电话圈。人名只包含字
母,不超过25个字符,且不重复。
解题方法:
首先用floyd求出传递闭包,即g[i][j]表示i是否直接或者间接给j打过电话,则当且仅当
g[i][j]=g[j][i]=1时二者处于一个电话圈。构造一个新图,在“在一个电话圈里”的两个人之间
连一条边,然后依次输出各个连通分量的所有人即可。
代码如下:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define cls(a, b) memset(a, b, sizeof(a))
map <string, int> mp;
vector <string> ans;
int n, m, id, vis[30], f[30][30];
void dfs(int u){
vis[u] = 1;
for(int i = 0; i < n; i++){
if(f[u][i] && f[i][u] && !vis[i]){
cout << ", " << ans[i];
dfs(i);
}
}
}
int main(){
int ks = 0;
while(scanf("%d%d", &n, &m) != EOF){
if(n == 0 && m == 0) break;
cls(vis, 0);
cls(f, 0);
mp.clear();
ans.clear();
id = 0;
for(int i = 0; i < m; i++){
string a, b;
cin >> a >> b;
if(!mp.count(a)){
mp[a] = id++;
ans.push_back(a);
}
if(!mp.count(b)){
mp[b] = id++;
ans.push_back(b);
}
int x = mp[a], y = mp[b];
f[x][y] = 1;
}
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
f[i][j] = (f[i][j] || (f[i][k] && f[k][j]));
}
}
}
if(ks > 0) printf("\n");
printf("Calling circles for data set %d:\n", ++ks);
for(int i = 0; i < n; i++){
if(!vis[i]){
cout << ans[i];
dfs(i);
cout << endl;
}
}
}
return 0;
}