Calling Circles UVA - 247 (Floyd passing closure)

Main idea:

In this paper, some graphs are given. The points in the graphs are connected by some directed edges. If two points can pass through each other, the two points belong to the same circle and output the circle of the whole graph.

Train of thought:

Use map to change a person's name into a number. Run Floyd to the number point to pass the closure. For example, if rela[i][j]==rela[j][i]==1, then I and j belong to the same circle. Then use concurrent query to save that two points belong to the same circle

#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
int relation[50][50];
map<string,int> mp;
vector<string> V;
int vis[50];
int n,m;
int fa[50];
void init()
{
	for(int i=1;i<=n;i++) fa[i]=i;
	memset(relation,0,sizeof(relation));
	mp.clear();
	V.clear();
	memset(vis,0,sizeof(vis));
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){int fx=find(x),fy=find(y);if(fx!=fy) fa[fx]=fy;}
void Floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				relation[i][j]|=(relation[i][k]&relation[k][j]);
			}
		}
	}
}
int main()
{
	string s1,s2;
	int tot=0;
	while(~scanf("%d%d",&n,&m)&&m){
		init();
		for(int i=1;i<=m;i++){
			cin>>s1>>s2;
			if(!mp.count(s1)) {V.push_back(s1),mp[s1]=V.size();}
			if(!mp.count(s2)) {V.push_back(s2),mp[s2]=V.size();}
			relation[mp[s1]][mp[s2]]=1;
		}
		Floyd();
		for(int i=1;i<=n;i++){
			for(int j=1;j<i;j++){
				if(relation[i][j]&relation[j][i])
				merge(i,j);
			}
		}
		if(tot++) cout<<endl;
		printf("Calling circles for data set %d:\n",tot);
		for(int i=1;i<=n;i++){
			if(fa[i]==i){
				cout<<V[i-1];vis[i]=1;
				for(int j=1;j<=n;j++){
					if(!vis[j]&&find(j)==i){
						cout<<", "<<V[j-1];
						vis[j]=1;
					}
				}
				cout<<endl;
			}
		}
	}

}

 

Added by ronald29x on Thu, 19 Dec 2019 17:57:34 +0200