【题意】
如果两个人互相打电话（直接或者间接），则说他们在同一个电话圈里。例如，\(a\)打给\(b\)，\(b\)打给\(c\)，\(c\)打给\(d\)，\(d\)打给\(a\)，则这四个人在同一个圈里；如果\(e\)打给\(f\)，而\(f\)不打给\(e\)，则不能推出\(e\)和\(f\)在同一个电话圈。输入\(n(n≤25)\)个人的\(m\)次电话，找出所有的电话圈。人名只包含字母，不超过\(25\)个字符，且不重复。
【算法】
\(Floyd\text{传递闭包}\)
【分析】
首先用\(Floyd\)求出传递闭包，即g[i][j]表示i是否直接或间接向j打过电话，当且仅当g[i][j]=g[j][i]=1时二者处于同一个电话圈。构造一个新图，在“一个电话圈里”的两个人之间连一条边，然后依次输出各个联通分量的所有人即可。
【代码】
#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
string st[30];
string st1,st2;
bool g[30][30];
bool used[30];
int sum;
int n,m;
int T;
int main()
{
cin>>n>>m;
while(1)
{
sum=0;
T++;
//cout<<T<<endl;memset(g,0,sizeof(g));
memset(used,0,sizeof(used));
mp.clear();
for(int i=1;i<=m;i++)
{
cin>>st1>>st2;
if(!mp[st1])
{
mp[st1]=++sum;
st[sum]=st1;
}
if(!mp[st2])
{
mp[st2]=++sum;
st[sum]=st2;
}
g[mp[st1]][mp[st2]]=1;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
g[i][j]=g[i][j] || (g[i][k] && g[k][j]);
}
}
}
printf("Calling circles for data set %d:\n",T);
/*for(int i=1;i<=n;i++)
cout<<st[i]<<" ";cout<<endl;*/
for(int i=1;i<=n;i++)
{
if(!used[i])
{
cout<<st[i];
used[i]=1;
for(int j=1;j<=n;j++)
{
if(g[i][j]&&g[j][i]&&!used[j])
{
cout<<", "<<st[j];
used[j]=1;
}
}
cout<<endl;
}
}
cin>>n>>m;
if(n||m)cout<<endl;
else break;
}
return 0;
}
刘汝佳大法好！
