首页 > 代码库 > 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)