Calling Circles[floyd求传递闭包]

传送门
首先用floyd求出传递闭包，即$g[i][j]$表示$i$是否直接或者间接给$j$打过电话，则当且仅当 $g[i][j]=g[j][i]=1$时二者处于一个电话圈。构造一个新图，在在一个电话圈里的两个人之间 连一条边，然后依次输出各个连通分量的所有人即可

#includeiostream
#includevector
#includestring
#includemap
#includecstdio
#includealgorithm
#includecstring
using namespace std;

const int N=30;

int g[N][N];
bool vis[N];
vectorstring s;
mapstring,intmp;
int n,m;

#define bg begin
#define pb push_back


void dfs(int u) {
  vis[u]=true;
  for(int i=0;in;i++) {
     if(!vis[i]g[u][i]g[i][u]) {
        cout  ", " s[i];
        dfs(i);
     }
  }
}

int main(){
	int kase=0;
	while(cinnm,m+n){
		s.clear();
		
		memset(vis,0,sizeof(vis));
		memset(g,0,sizeof(g));
		mp.clear();
		
		for(int i=0;im;i++){
			string a,b;
			cinab;
			int cnt=0;
			if(!count(s.bg(),s.end(),a)){
				s.pb(a),mp[a]=s.size()-1;
			}
			if(!count(s.bg(),s.end(),b)){
				s.pb(b),mp[b]=s.size()-1;
			}
			g[mp[a]][mp[b]]=1;
		}
		for(int k=0;kn;k++)
			for(int i=0;in;i++)
				for(int j=0;jn;j++)
					g[i][j]=g[i][j]||(g[i][k]g[k][j]);
		printf("Calling circles for data set %d:\n",++kase);
		for(int i=0;in;i++){
			if(!vis[i]){
				couts[i];
				dfs(i);
				cout"\n";
			}
		}
	}
}