Uva 247 电话圈——Floyd算法求传递闭包

网友投稿 569 2022-11-29

Uva 247 电话圈——Floyd算法求传递闭包

Uva 247 电话圈——Floyd算法求传递闭包

Floyd求传递闭包时注意将d[i][i]初始化为1，其余为0，然后再向其中输入值

dfs输出，为了方便维护输出数据先用数组存了一下

写的比较乱，幸好这题没什么坑

#include #include #include #include #include #include using namespace std;map link;map linkr;int G1[50][50];int G2[50][50];int cnt;int n, m;vector output[50];int vis[50];int pos;void dfs(int i) { output[pos].push_back(i); for (int j = 1; j <= n; j++) { if (!vis[j] && G2[i][j]) { vis[j] = 1; dfs(j); } }}void init() { link.clear(); linkr.clear(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) G1[i][j] = 1; else G1[i][j] = 0; } } memset(G2, 0, sizeof(G2)); for (int i = 0; i < 50; i++) { output[i].clear(); } memset(vis, 0, sizeof(vis)); cnt = 0; pos = 1;}int main(){ int flag = 0; while (cin >> n >> m && n && m) { init(); string name1, name2; while (m--) { cin >> name1 >> name2; if (linkr[name1] == 0) { ++cnt; link[cnt] = name1; linkr[name1] = cnt; } if (linkr[name2] == 0) { ++cnt; link[cnt] = name2; linkr[name2] = cnt; } int a = linkr[name1], b = linkr[name2]; G1[a][b] = 1; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { G1[i][j] = G1[i][j]||(G1[i][k] && G1[k][j]); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (G1[i][j] && G1[j][i]) { G2[i][j] = G2[j][i] = 1; } } } if (flag) cout << endl; cout << "Calling circles for data set " << ++flag << ":" << endl; for (int i = 1; i <= n; i++) { if (!vis[i]) { vis[i] = 1; dfs(i); pos++; } } for (int i = 1; i < pos; i++) { int flag2 = 0; int len = output[i].size(); for (int j = 0; j < len; j++) { if (flag2++) cout << ", "; cout << link[output[i][j]]; } cout << endl; } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：算法 输入 数据 输出
上一篇:UVa 1626 括号序列——区间DP
下一篇:Uva 10048 噪音恐惧症——Floyd变形
相关文章

 发表评论

暂时没有评论，来抢沙发吧~