首页 > 代码库 > UVa 247 (传递闭包) Calling Circles

UVa 247 (传递闭包) Calling Circles

2024-10-24 09:49:39   213人阅读

题意：

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

分析：

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

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

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

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

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

这样就避免了cin cout

技术分享
 1 #include <cstdio> 2 #include <vector> 3 #include <string> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7  8 const int maxn = 30; 9 int n;10 bool R[maxn][maxn], vis[maxn];11 char s1[99], s2[99];12 vector<string> names;13 14 int ID(const string& s)15 {16     for(int i = 0; i < names.size(); ++i)17         if(names[i] == s) return i;18     names.push_back(s);19     return names.size() - 1;20 }21 22 void dfs(int u)23 {24     vis[u] = true;25     for(int v = 0; v < n; ++v)26         if(!vis[v] && R[u][v] && R[v][u])27         {28             cout << ", " << names[v];29             dfs(v);30         }31 }32 33 int main()34 {35     //freopen("in.txt", "r", stdin);36     int kase = 0, m;37     while(scanf("%d%d", &n, &m) == 2 && n)38     {39         names.clear();40         memset(R, false, sizeof(R));41         if(kase) printf("\n");42         printf("Calling circles for data set %d:\n", ++kase);43         for(int i = 0; i < n; ++i) R[i][i] = true;44         for(int i = 0; i < m; ++i)45         {46             scanf("%s%s", s1, s2);47             R[ID(s1)][ID(s2)] = true;48         }49         for(int k = 0; k < n; ++k)50             for(int i = 0; i < n; ++i)51                 for(int j = 0; j < n; ++j)52                     R[i][j] |= R[i][k] && R[k][j];53         memset(vis, false, sizeof(vis));54         for(int i = 0; i < n; ++i) if(!vis[i])55         {56             printf("%s", names[i].c_str());57             dfs(i);58             printf("\n");59         }60     }61 62     return 0;63 }
代码君

 

UVa 247 (传递闭包) Calling Circles


联系
我们