Floyd有向图的传递闭包-UVA - 247

2019-11-06 08:39:53

字体：大中小

来源：转载

供稿：网友

//有向图的传递闭包#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<vector>#include<set>#include<map>#include<algorithm>using namespace std;vector<string> vt;map<string,int> mp;const int maxn=25+5;int G[maxn][maxn];int d[maxn][maxn];int N,M;int vis[maxn];void init(){ mp.clear(); memset(G,0,sizeof(G)); vt.clear(); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis));}void dfs(int a){ vis[a]=1; for(int i=0;i<N;i++){ if(G[a][i]&&G[i][a]){ if(!vis[i]){ cout<<", "<<vt[i]; dfs(i); } } }}int main(){ int cas=0; while(cin>>N>>M&&N){ init(); string s1,s2; for(int i=0;i<M;i++){ cin>>s1>>s2; if(!mp.count(s1)){ vt.push_back(s1); mp[s1]=vt.size()-1; } if(!mp.count(s2)){ vt.push_back(s2); mp[s2]=vt.size()-1; } G[mp[s1]][mp[s2]]=1; } //有向图的传递闭包 for(int k=0;k<N;k++) for(int i=0;i<N;i++) for(int j=0;j<N;j++) G[i][j]=G[i][j]||(G[i][k]&&G[k][j]); //dfs if(cas)cout<<endl; PRintf("Calling circles for data set %d:/n",++cas); for(int i=0;i<N;i++){ if(!vis[i]){ cout<<vt[i]; dfs(i); cout<<endl; } } } return 0;}

上一篇：linux下分区挂载

下一篇：HTML学习笔记（四）--URL/颜色/快速参考