If you’ve seen television commercials for long-distance phone
companies lately, you’ve noticed that many companies have been
spending a lot of money trying to convince people that they provide
the best service at the lowest cost. One company has \calling
circles.” You provide a list of people that you call most frequently.
If you call someone in your calling circle (who is also a customer of
the same company), you get bigger discounts than if you call outside
your circle. Another company points out that you only get the big
discounts for people in your calling circle, and if you change who you
call most frequently, it’s up to you to add them to your calling
circle. LibertyBell Phone Co. is a new company that thinks they have
the calling plan that can put other companies out of business.
LibertyBell has calling circles, but they gure out your calling
circle for you. This is how it works. LibertyBell keeps track of all
phone calls. In addition to yourself, your calling circle consists
of all people whom you call and who call you, either directly or
indirectly. For example, if Ben calls Alexander, Alexander calls
Dolly, and Dolly calls Ben, they are all within the same circle.
If Dolly also calls Benedict and Benedict calls Dolly, then
Benedict is in the same calling circle as Dolly, Ben, and
Alexander. Finally, if Alexander calls Aaron but Aaron doesn’t call
Alexander, Ben, Dolly, or Benedict, then Aaron is not in the circle.
You’ve been hired by LibertyBell to write the program to determine
calling circles given a log of phone calls between people. Input The
input le will contain one or more data sets. Each data
set begins with a line containing two integers, n and m . The
rst integer, n , represents the number of different people who are in
the data set. The maximum value for n is 25. The remainder of the
data set consists of m lines, each representing a phone call. Each
call is represented by two names, separated by a single space. Names
are rst names only (unique within a data set), are case sensitive,
and consist of only alphabetic characters; no name is longer than 25
letters. For example, if Ben called Dolly, it would be represented in
the data le as Ben Dolly Input is terminated by values of zero (0)
for n and m . Output For each input set, print a header line with the
data set number, followed by a line for each calling circle in that
data set. Each calling circle line contains the names of all the
people in any order within the circle, separated by comma-space (a
comma followed by a space). Output sets are separated by blank lines.
用floyd传递闭包，然后dfs，如果两个点互相可达就在一个集合里。
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<iostream>
using namespace std;
map<string,int> mp;
string str[30];
int n,m,f[30][30],vis[30];
void init()
{int i,cnt=0;string s1,s2;memset(f,0,sizeof(f));memset(vis,0,sizeof(vis));mp.clear();for (i=1;i<=m;i++){cin>>s1>>s2;if (!mp.count(s1)) mp[s1]=++cnt,str[cnt]=s1;if (!mp.count(s2)) mp[s2]=++cnt,str[cnt]=s2;f[mp[s1]][mp[s2]]=1;}
}
void solve()
{int i,j,k;for (k=1;k<=n;k++)for (i=1;i<=n;i++)for (j=1;j<=n;j++)f[i][j]|=f[i][k]&f[k][j];
}
void dfs(int u)
{int v;for (v=1;v<=n;v++)if (f[u][v]&&f[v][u]&&!vis[v]){cout<<", "<<str[v];vis[v]=1;dfs(v);}
}
int main()
{int i,K=0;while (cin>>n>>m&&n){init();solve();if (K) cout<<endl;cout<<"Calling circles for data set "<<++K<<":"<<endl;for (i=1;i<=n;i++)if (!vis[i]){cout<<str[i];vis[i]=1;dfs(i);cout<<endl;}}
}