首页 > 代码库 > UVa247 Calling Circles (Floyd,DFS)
UVa247 Calling Circles (Floyd,DFS)
链接:http://bak3.vjudge.net/problem/UVA-247
分析:先用Floyd求出有向图的传递闭包,然后用DFS求出各个联通分量即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <string> 5 using namespace std; 6 7 vector<string> names; 8 int ID(const string& s) { 9 for (int i = 0; i < names.size(); i++)10 if (names[i] == s) return i;11 names.push_back(s);12 return names.size() - 1;13 }14 15 const int maxn = 25 + 5;16 int n, m;17 int vis[maxn];18 int d[maxn][maxn];19 void dfs(int u) {20 vis[u] = 1;21 for (int v = 0; v < n; v++)22 if (!vis[v] && d[u][v] && d[v][u]) {23 printf(", %s", names[v].c_str());24 dfs(v);25 }26 }27 28 int main() {29 int kase = 0;30 char s1[99], s2[99];31 while (scanf("%d%d", &n, &m) == 2 && n) {32 names.clear();33 memset(d, 0, sizeof(d));34 for (int i = 0; i < n; i++) d[i][i] = 1;35 while (m--) {36 scanf("%s%s", s1, s2);37 d[ID(s1)][ID(s2)] = 1;38 }39 for (int k = 0; k < n; k++)40 for (int i = 0; i < n; i++)41 for (int j = 0; j < n; j++)42 d[i][j] |= d[i][k] && d[k][j];43 if (kase > 0) printf("\n");44 printf("Calling circles for data set %d:\n", ++kase);45 memset(vis, 0, sizeof(vis));46 for (int i = 0; i < n; i++)47 if (!vis[i]) {48 printf("%s", names[i].c_str());49 dfs(i);50 printf("\n");51 }52 }53 return 0;54 }
UVa247 Calling Circles (Floyd,DFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。