该题恰好用到刚刚讲到的Floyd求传递闭包 ， 因为该题的数据量不是很大，， 要是大了估计就要用其他方法了 。 但是这毕竟是一个很简单易写的算法 。
求出传递闭包之后就用并查集将在一个电话圈的人合并在一起，最后输出 。
细节参见代码：
#include<bits/stdc++.h>using namespace std;int n,m,d[30][30],par[30],kase = 0;string s1,s2;map<string , int > p;map<int,int> pp;struct node {string s;int id;node(string s="",int id=0) : s(s),id(id) {}}a[30];int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }void Floyd() { //求传递闭包for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j] = d[i][j]||(d[i][k]&&d[k][j]);}int main() {bool flage = true;while(~scanf("%d%d",&n,&m)) {if(!n && !m) return 0;p.clear(); pp.clear();if(!flage) printf("\n");else flage = false;memset(d,0,sizeof(d));int cnt = 0;for(int i=0;i<m;i++) {cin>>s1>>s2;if(!p.count(s1)) {a[cnt] = node(s1,cnt);p[s1] = cnt; ++cnt;}if(!p.count(s2)) {a[cnt] = node(s2,cnt);p[s2] = cnt; ++cnt;}d[p[s1]][p[s2]] = 1;}Floyd();vector<int> res; //用并查集合并集合for(int i=0;i<cnt;i++) par[i] = i;for(int i=0;i<cnt;i++) {for(int j=i+1;j<cnt;j++) {if(d[i][j]&&d[j][i]) {int x = find(i) , y = find(j);if(x != y) par[x] = y;}}}printf("Calling circles for data set %d:\n",++kase);for(int i=0;i<cnt;i++) { //按父节点找到在相应集合中的人int x = find(i);if(!pp.count(x)) {pp[x] = 1; res.push_back(x);}}int len = res.size(); //输出for(int i=0;i<len;i++) {bool ok = true;int v = res[i];for(int j=0;j<cnt;j++) {int x = find(j);if(x == v) {if(ok) printf("%s",a[j].s.c_str()) , ok = false;else printf(", %s",a[j].s.c_str());}}printf("\n");}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
积极的人在每一次忧患中都看到一个机会，
