Calling Circles[floyd求传递闭包]

传送门
首先用floyd求出传递闭包,即 g [ i ] [ j ] g[i][j] g[i][j]表示 i i i是否直接或者间接给 j j j打过电话,则当且仅当 g [ i ] [ j ] = g [ j ] [ i ] = 1 g[i][j]=g[j][i]=1 g[i][j]=g[j][i]=1时二者处于一个电话圈。构造一个新图,在在一个电话圈里的两个人之间 连一条边,然后依次输出各个连通分量的所有人即可

#includeiostream
#includevector
#includestring
#includemap
#includecstdio
#includealgorithm
#includecstring
using namespace std;

const int N=30;

int g[N][N];
bool vis[N];
vectorstring s;
mapstring,intmp;
int n,m;

#define bg begin
#define pb push_back


void dfs(int u) {
  vis[u]=true;
  for(int i=0;in;i++) {
     if(!vis[i]g[u][i]g[i][u]) {
        cout  ", " s[i];
        dfs(i);
     }
  }
}

int main(){
	int kase=0;
	while(cinnm,m+n){
		s.clear();
		
		memset(vis,0,sizeof(vis));
		memset(g,0,sizeof(g));
		mp.clear();
		
		for(int i=0;im;i++){
			string a,b;
			cinab;
			int cnt=0;
			if(!count(s.bg(),s.end(),a)){
				s.pb(a),mp[a]=s.size()-1;
			}
			if(!count(s.bg(),s.end(),b)){
				s.pb(b),mp[b]=s.size()-1;
			}
			g[mp[a]][mp[b]]=1;
		}
		for(int k=0;kn;k++)
			for(int i=0;in;i++)
				for(int j=0;jn;j++)
					g[i][j]=g[i][j]||(g[i][k]g[k][j]);
		printf("Calling circles for data set %d:\n",++kase);
		for(int i=0;in;i++){
			if(!vis[i]){
				couts[i];
				dfs(i);
				cout"\n";
			}
		}
	}
}
 
最新回复(0)
/jishu79Ebio14l6EnsJ4RYxJF_2FDOCReYKtqFHhM_2F1ew_3D_3D4681548
8 简首页