首页 > 代码库 > Openjudge 百练 / 2524 - 宗教信仰 [并查集]
Openjudge 百练 / 2524 - 宗教信仰 [并查集]
URL: http://bailian.openjudge.cn/practice/2524/
【描述】
世界上有许多宗教,你感兴趣的是你学校里的同学信仰多少种宗教。
你的学校有n名学生(0 < n <= 50000),你不太可能询问每个人的宗教信仰,因为他们不太愿意透露。但是当你同时找到2名学生,他们却愿意告诉你他们是否信仰同一宗教,你可以通过很多这样的询问估算学校里的宗教数目的上限。你可以认为每名学生只会信仰最多一种宗教。
【输入】
输入包括多组数据。
每组数据的第一行包括n和m,0 <= m <= n(n-1)/2,其后m行每行包括两个数字i和j,表示学生i和学生j信仰同一宗教,学生被标号为1至n。输入以一行 n = m = 0 作为结束。
【输出】
对于每组数据,先输出它的编号(从1开始),接着输出学生信仰的不同宗教的数目上限。
【样例输入】
10 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 10 4 2 3 4 5 4 8 5 8 0 0
【样例输出 】
Case 1: 1 Case 2: 7
OI C++ Code:
#include <iostream> #include <cstring> using namespace std; int father[50000], root_sum[50000]; int get_root(int child) { while (father[child] != child) { child = father[child]; } return child; } int main() { int cnt = 0; while (true) { int n, m; cin >> n >> m; if (m == 0 && n == 0) { break; } ++cnt; for (int i = 0; i < n; ++i) { father[i] = i; } for (int k = 0; k < m; ++k) { int i, j; cin >> i >> j; --i; --j; father[i] = get_root(i); father[j] = get_root(j); if (father[i] != father[j]) { father[father[i]] = father[j]; } } memset(root_sum, 0, sizeof(root_sum)); for (int i = 0; i < n; ++i) { ++root_sum[get_root(i)]; } int root_num = 0; for (int i = 0; i < n; ++i) { if (root_sum[i] != 0) { ++root_num; } } cout << "Case " << cnt << ": " << root_num << endl; } return 0; }
C++ Code:
#include <iostream> #include <vector> using namespace std; int get_root(const vector<int> &father, int child) { while (father[child] != child) { child = father[child]; } return child; } int main() { int cnt = 0; while (true) { int n, m; cin >> n >> m; if (m == 0 && n == 0) { break; } ++cnt; vector<int> father(n); for (int i = 0; i < n; ++i) { father[i] = i; } for (int k = 0; k < m; ++k) { int i, j; cin >> i >> j; --i; --j; father[i] = get_root(father, i); father[j] = get_root(father, j); if (father[i] != father[j]) { father[father[i]] = father[j]; } } vector<int> root_sum(n, 0); for (int i = 0; i < n; ++i) { ++root_sum[get_root(father, i)]; } int root_num = 0; for (int i = 0; i < n; ++i) { if (root_sum[i] != 0) { ++root_num; } } cout << "Case " << cnt << ": " << root_num << endl; } return 0; }
Openjudge 百练 / 2524 - 宗教信仰 [并查集]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。