互相可以打电话是一个传递关系,所以Floyd求传递封包,dfs找一个尽量大的圈。
#includeusing namespace std;const int maxn = 25;map mp;map ::iterator it;vector names;bool d[maxn][maxn];int ID(const string& s){ if((it = mp.find(s))!=mp.end()) return it->second; mp.insert(make_pair(s,names.size())); names.push_back(s); return names.size()-1;}bool vis[maxn];int n,m;void dfs(int u){ vis[u] = true; for(int i = 0; i < n; i++){ if(!vis[i] && d[u][i] && d[i][u]){ printf(", %s",names[i].c_str()); dfs(i); } }}int main(){ //freopen("in.txt","r",stdin); char s1[50],s2[50]; int kas = 0; while(scanf("%d%d",&n,&m),n){ if(kas) putchar('\n'); memset(d,0,sizeof(d)); names.clear(); mp.clear(); while(m--) { scanf("%s%s",s1,s2); d[ID(s1)][ID(s2)] = true; } for(int i = 0; i < n; i++) d[i][i] = true; for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){ d[i][j] |= d[i][k]&&d[k][j]; } printf("Calling circles for data set %d:\n",++kas); fill(vis,vis+n,0); for(int i = 0; i < n; i++){ if(!vis[i]){ printf("%s",names[i].c_str()); dfs(i); putchar('\n'); } } } return 0;}