首页 > 代码库 > UVa 247 电话圈（Floyd传递闭包）
UVa 247 电话圈（Floyd传递闭包）
https://vjudge.net/problem/UVA-247
题意：
如果两个人相互打电话，则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这4个人在同一个圈里；如果e打给f但f不打给e，则不能推出e和f在同一个电话圈里，输出所有电话圈。
思路：
通过Floyd求一个传递闭包。最后dfs输出每一个电话圈即可。
传递闭包的求法：
1 for (int k = 0; k < n;k++)2 for (int i = 0; i < n;i++)3 for (int j = 0; j < n; j++)4 d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<algorithm> 5 #include<map> 6 #include<vector> 7 using namespace std; 8 9 int n, m;10 int d[30][30];11 string s1, s2;12 map<string, int> ID;13 vector<string> name;14 int vis[30];15 16 void dfs(int k)17 {18 vis[k] = 1;19 for (int i = 0; i < n; i++)20 {21 if (d[k][i] && d[i][k])22 {23 if (!vis[i])24 {25 cout << ", " << name[i];26 dfs(i);27 }28 }29 }30 }31 32 int main()33 {34 //freopen("D:\\txt.txt", "r", stdin);35 int kase = 1;36 while (scanf("%d%d", &n, &m))37 {38 if (n == 0 && m == 0) break;39 if (kase > 1) printf("\n");40 memset(d, 0, sizeof(d));41 memset(vis, 0, sizeof(vis));42 ID.clear();43 name.clear();44 int cnt = 0;45 for (int i = 0; i < m; i++)46 {47 cin >> s1 >> s2;48 if (!ID.count(s1))49 {50 ID[s1] = cnt++;51 name.push_back(s1);52 }53 if (!ID.count(s2))54 {55 ID[s2] = cnt++;56 name.push_back(s2);57 }58 int x = ID[s1];59 int y = ID[s2];60 d[x][y] = 1;61 }62 63 for (int k = 0; k < n;k++)64 for (int i = 0; i < n;i++)65 for (int j = 0; j < n; j++)66 d[i][j] = d[i][j] || (d[i][k] && d[k][j]);67 68 printf("Calling circles for data set %d:\n", kase++);69 for (int i = 0; i < n; i++)70 {71 if (!vis[i])72 {73 cout << name[i];74 dfs(i);75 printf("\n");76 }77 }78 }79 return 0;80 }
UVa 247 电话圈（Floyd传递闭包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。