首页 > 代码库 > UVa 247 (传递闭包) Calling Circles
UVa 247 (传递闭包) Calling Circles
题意:
有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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。