算法
floyed+传递闭包
代码
#include<bits/stdc++.h> using namespace std; map<string,int>mp; string st[30]; string st1,st2; bool g[30][30]; bool used[30]; int sum; int n,m; int T; int main() { cin>>n>>m; while(1) { sum=0; T++; //cout<<T<<endl; memset(g,0,sizeof(g)); memset(used,0,sizeof(used)); mp.clear(); for(int i=1;i<=m;i++) { cin>>st1>>st2; if(!mp[st1]) { mp[st1]=++sum; st[sum]=st1; } if(!mp[st2]) { mp[st2]=++sum; st[sum]=st2; } g[mp[st1]][mp[st2]]=1;//map存字符串 } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { g[i][j]=g[i][j] || (g[i][k] && g[k][j]);//floyed传递闭包 } } } printf("Calling circles for data set %d:\n",T); /*for(int i=1;i<=n;i++) cout<<st[i]<<" ";cout<<endl;*/ for(int i=1;i<=n;i++) { if(!used[i]) { cout<<st[i]; used[i]=1; for(int j=1;j<=n;j++) { if(g[i][j]&&g[j][i]&&!used[j]) { cout<<", "<<st[j]; used[j]=1; } } cout<<endl;//输出每一个电话圈(集合) } } cin>>n>>m; if(n||m)cout<<endl; else break; } return 0; }
原文链接: https://www.cnblogs.com/ruanmowen/p/12720238.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/342703
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!