题目链接

题意：如果两个人互相打电话（直接或者间接），则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这四个人在同一个圈里；如果e打给f，而f不打给e，则不能推出e和f在同一个电话圈。输入n(n<=25)个人的m次电话，找出所有的电话圈。人名只包含字母，不超过25个字符，且不重复。

solution_1：tarjan求有向图SCC

#include <map>
#include <stack> 
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 50;vector<int> G[N];stack<int> S;
int dfn[N], low[N];
bool bl[N];
int id;
map<string,int> mp1;
map<int,string> mp2;
int tot=0;
int Hash(string str){if( mp1.count(str) ) return mp1[str];mp1[str]=++tot;mp2[tot]=str;return tot;
} 
void dfs(int u){dfn[u]=low[u]=++id;S.push(u);bl[u]=true;for ( int i=0; i<G[u].size(); i++ ){int v=G[u][i];if( !dfn[v] ) {dfs(v);low[u]=min(low[u],low[v]);} else if( bl[v] ){low[u]=min(low[u],dfn[v]);}}if( low[u]==dfn[u] ){int ok=0;while( !S.empty()){int x=S.top(); S.pop();bl[x]=false;if( !ok ) cout<<mp2[x], ok=1;else cout<<", "<<mp2[x];if( x==u ) {break;}}cout<<"\n";}
}void find_scc(int n){memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(bl,0,sizeof(bl));id=0;for ( int i=1; i<=n; i++ )if( !dfn[i] ) dfs(i); 
}int n, m;
int main(){int k=0;while( ~scanf("%d%d", &n, &m ) && (n||m) ){if( k ) cout<<"\n";printf("Calling circles for data set %d:\n", ++k);  for ( int i=0; i<N; i++ ) G[i].clear();tot=0;mp1.clear(); mp2.clear();for ( int i=1; i<=m; i++ ){string s1,s2;cin>>s1>>s2;int x=Hash(s1), y=Hash(s2);G[x].push_back(y);  }find_scc(n);}
}

solution_2: Floyed求传递闭包

#include <map>
#include <stack> 
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 30;
int a[N][N];
bool vis[N];
map<string,int> mp1;
map<int,string> mp2;
int tot=0;
int Hash(string str){if( mp1.count(str) ) return mp1[str];mp1[str]=++tot;mp2[tot]=str;return tot;
} 
int n, m;
int main(){int k=0;while( ~scanf("%d%d", &n, &m ) && (n||m) ){if( k ) cout<<"\n";printf("Calling circles for data set %d:\n", ++k);  memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));tot=0;mp1.clear(); mp2.clear();for ( int i=1; i<=m; i++ ){string s1,s2;cin>>s1>>s2;int x=Hash(s1), y=Hash(s2);a[x][y]=1;}for ( int k=1; k<=n; k++ )for ( int i=1; i<=n; i++ )for ( int j=1; j<=n; j++ )a[i][j]=a[i][j] || (a[i][k]&&a[k][j]);for ( int i=1; i<=n; i++ ){if( vis[i] ) continue;vis[i]=1;cout<<mp2[i];for ( int j=1; j<=n; j++ ) if( !vis[j] && a[i][j] && a[j][i] ) {vis[j]=1;cout<<", "<<mp2[j];}cout<<"\n";}}
}