题目链接:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=183
求出传递闭包,知道两个人之间能否直接或间接互相联系,如果能互相联系则在一个电话圈里,建新图输出每个连通分量即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 110;
int n, m, tot;
int d[maxn][maxn];
map<string, int> mp;
vector<string> names;
int h[maxn], cnt = 0;
struct Edge{
int to, next;
}e[maxn * maxn * 2];
void add(int u, int v){
e[++cnt].to = v;
e[cnt].next = h[u];
h[u] = cnt;
}
int ID(const string s){
if(mp.count(s) != 0){
return mp[s];
} else{
names.push_back(s);
mp[s] = ++tot;
return tot;
}
}
int f = 0;
int vis[maxn];
void dfs(int u){
if(vis[u]) return;
if(f) printf(", ");
f = 1;
printf("%s", names[u-1].c_str());
vis[u] = 1;
for(int i = h[u] ; i != -1 ; i = e[i].next){
int v = e[i].to;
dfs(v);
}
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘){ s = s * 10 + ch - ‘0‘; ch = getchar(); } return s * f; }
int main(){
int flag = 0, kase = 0;
while(scanf("%d%d", &n, &m) && (n || m)){
if(flag) printf("\n");
flag = 1;
printf("Calling circles for data set %d:\n", ++kase);
memset(vis, 0, sizeof(vis));
memset(h, -1, sizeof(h));
cnt = 0; tot = 0;
memset(d, 0, sizeof(d));
memset(vis, 0, sizeof(vis));
mp.clear();
names.clear();
char s1[100], s2[100];
for(int i = 1 ; i <= n ; ++i) d[i][i] = 1;
for(int i = 1 ; i <= m ; ++i){
scanf("%s%s", s1, s2);
d[ID(s1)][ID(s2)] = 1;
}
for(int k = 1 ; k <= n ; ++k){
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= n ; ++j){
d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
}
}
}
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= n ; ++j){
if(d[i][j] && d[j][i]){
add(i, j); add(j, i);
}
}
}
for(int i = 1 ; i <= n ; ++i){
if(!vis[i]) {
f = 0;
dfs(i);
printf("\n");
}
}
}
return 0;
}