题目链接: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;
}