UVa 247 (传递闭包) Calling Circles

题意：

有n个人m通电话，如果有两个人相互打电话(直接或间接)则在同一个电话圈里。输出所有电话圈的人的名单。

分析：

根据打电话的关系，可以建一个有向图，然后用Warshall算法求传递闭包。

最后输出是辅助一个标记数组，用DFS输出的，这个办法挺巧妙的。

本来我原来的想法是，用并查集求所有的连通分量，然后再好多次循环找连通分量一致的名字输出，那样太麻烦了。

ios::sync_with_stdio(false);这个最好不要随便用，可能会产生某些副作用。

字符指针是可以传给string对象作参数的函数的，string对象有个c_str()函数返回一个字符指针，因此也可以用printf输出。

这样就避免了cin cout

 #include <cstdio>

 #include <vector>

 #include <string>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int maxn = ;

 int n;

 bool R[maxn][maxn], vis[maxn];

 char s1[], s2[];

 vector<string> names;

 int ID(const string& s)

 {

     for(int i = ; i < names.size(); ++i)

         if(names[i] == s) return i;

     names.push_back(s);

     return names.size() - ;

 }

 void dfs(int u)

 {

     vis[u] = true;

     for(int v = ; v < n; ++v)

         if(!vis[v] && R[u][v] && R[v][u])

         {

             cout << ", " << names[v];

             dfs(v);

         }

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int kase = , m;

     while(scanf("%d%d", &n, &m) ==  && n)

     {

         names.clear();

         memset(R, false, sizeof(R));

         if(kase) printf("\n");

         printf("Calling circles for data set %d:\n", ++kase);

         for(int i = ; i < n; ++i) R[i][i] = true;

         for(int i = ; i < m; ++i)

         {

             scanf("%s%s", s1, s2);

             R[ID(s1)][ID(s2)] = true;

         }

         for(int k = ; k < n; ++k)

             for(int i = ; i < n; ++i)

                 for(int j = ; j < n; ++j)

                     R[i][j] |= R[i][k] && R[k][j];

         memset(vis, false, sizeof(vis));

         for(int i = ; i < n; ++i) if(!vis[i])

         {

             printf("%s", names[i].c_str());

             dfs(i);

             printf("\n");

         }

     }

     return ;

 }

代码君