题目大意:a和b打电话,b和c打电话可以构成一个电话圈,a和b打电话,b不和a打电话这样不算构成电话圈(也就是说这是一个有向图,因为这个wa一次),然后要你求可以构成圈的成员。思路:先对输入的字符串转化为数字(难点),然后求传递闭包,最后遍历图。
技巧:将字符串存储在who数组里面,字符对应数子用map<string,int>完成,这个思路我看别人写的自己没想到,不禁落下没有技术的眼泪。
总结:虽然这题看了别人的代码但是给我自己的收获确实不小,首先就是给字符串编号的技巧还不错,然后将map和vector用的非常巧妙,包括遍历也是,判断充分体现的传递闭包的对称性。
代码:

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a[30][30];
int vis[30];
string who[30];

void floyd(){
	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]);
			}
		}
	}
}
void ini(){
	memset(a,0,sizeof(a)); 
	memset(vis,0,sizeof(vis));
}
int main()
{
	int k=0;
	while(cin>>n>>m&&(n||m)){
		if(k)cout<<endl;
		ini();
		string name1,name2;
		map<string,int>id;
		vector<int>st[30];
		int cnt=0;
		for(int i=1;i<=m;i++){
			cin>>name1>>name2;
			if(!id[name1])id[name1]=++cnt,who[cnt]=name1;
			if(!id[name2])id[name2]=++cnt,who[cnt]=name2;
			a[id[name1]][id[name2]]=1;
	    }
		floyd();
		cout<<"Calling circles for data set "<<++k<<":"<<endl;
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				cout<<who[i];
				vis[i]=1;
				for(int j=1;j<=n;j++){
					if(a[i][j]&&a[j][i]&&!vis[j]){
						cout<<", "<<who[j];
						vis[j]=1;
					}
				}
			cout<<endl;
			}	
		}
	}
}