Calling Circles(UVa 247)(Floyd 算法)

用Floyd算法求出传递闭包,然后用dfs求出每条连通分量。注意其中用到的几个小技巧:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<map> using namespace std;
vector<string> name;///存储名字
int connect[30][30],vis[30],m,n; int id(string& s) {///用函数标记每个名字对应的id
for(int i=0;i<name.size();i++)
if(name[i]==s) return i;
name.push_back(s);
return name.size() - 1;
} void dfs(int u){///用深搜查找连通分量
vis[u]=1;
for(int v=0;v<n;v++)
if(!vis[v]&&connect[u][v]&&connect[v][u]) {
cout<<", "<<name[v];
dfs(v);
}
} int main()
{
int kase=0;
while(~scanf("%d%d",&n,&m)&&n&&m){
string s1,s2;
int t=0;
memset(connect,0,sizeof(connect));
name.clear();
for(int i=0;i<m;i++){///输入
cin>>s1;
cin>>s2;
connect[id(s1)][id(s2)]=1;///小技巧
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
connect[i][j]=connect[i][j]||(connect[i][k]&&connect[k][j]);///Floyd if(kase>0) printf("\n");
printf("Calling circles for data set %d:\n", ++kase); memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++){
if(!vis[i]){
cout<<name[i];
dfs(i);
printf("\n");
}
}
}
return 0;
}

  

上一篇:python安装出现的证书问题


下一篇:UVa 247 - Calling Circles(Floyd求有向图的传递闭包)