题目:
思路:
利用Floyd求传递闭包(mp[i][j] = mp[i][j]||(mp[i][k]&&mp[k][j]);),当mp[i][j]=1&&mp[j][i]=1的时候,i 和 j就是在同一个电话圈中。
代码:
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1000000000
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
const int maxn = ;
int n,m,cnt;
map<string,int> idx;
string name1,name2;
string st[maxn];
int mp[maxn][maxn],vis[maxn]; int id(string name){
if(!idx.count(name)){
idx[name] = cnt;
st[cnt] = name;
return cnt++;
}
return idx[name];
} int main(){
//FRE();
int kase = ;
while(scanf("%d%d",&n,&m) && n){
memset(mp,,sizeof(mp));
memset(vis,,sizeof(vis));
idx.clear();
cnt=; for(int i=; i<m; i++){
cin>>name1>>name2;
int p = id(name1),q = id(name2);
mp[p][q] = ;
} for(int k=; k<n; k++){
for(int i=; i<n; i++){
for(int j=; j<n; j++){
mp[i][j] = mp[i][j]||(mp[i][k]&&mp[k][j]);
}
}
}
if(kase)cout<<endl;
cout<<"Calling circles for data set "<<++kase<<":"<<endl;
for(int i=; i<n; i++){
if(vis[i]==){
cout<<st[i];
vis[i] = ;
for(int j=i+; j<n; j++){
if(vis[j]==&&mp[i][j]&&mp[j][i]){
cout<<", "<<st[j];
vis[j]=;
}
}
cout<<endl;
}
}
}
return ;
}