无所不在的宗教
时间限制： 5000MS 内存限制： 65536K
总提交数： 37180 接受： 17719
描述
今天世界上有这么多不同的宗教，很难跟踪他们。你有兴趣了解你大学中
有多少不同宗教的学生相信， 你知道你大学里有n个学生（0 <n <= 50000）。要求每个学生都有宗教信仰是不可行的。此外，许多学生不舒服地表达自己的信仰。避免这些问题的一个方法是询问m（0 <= m <= n（n-1）/ 2）对学生，并询问他们是否相信同一个宗教（例如他们可能知道他们是否同时参加教会）。从这些数据，你可能不知道每个人相信什么，但你可以了解在校园里有多少不同的宗教可能代表的上限。
输入
输入包括多种情况。每个案例以一行指定整数n和m开始。接下来的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
样品输出
Case1：1
Case2：7
其实这就是一道并查集的题目，如果你还不知道并查集是什么，那就先看我的另一篇文章⤵
http://www.cnblogs.com/horizonice/p/3658176.html
那大家知道了并查集的算法，那么这道题应该有思路了吧？
其实思路很简单，每输入一个i，j表示i，j相信同一个宗教，那么就把他们归入同一个 并查集就行了，最后统计一下有多少个并查集输出就over了；
完整代码如下⤵
#include<iostream>
#include<cstdio>
using namespace std;
int n, m, x, y;
int f[50010] = {};//f[i]为第i个节点的父亲
void inti() {
for (int i = 1; i <= n; i++) {
f[i] = i;
}
return;
}
//初始化f数组，让每个节点所处的并查集都是自己，也是每个并查集必须写上的
int dfs(int t) {
if (f[t] == t) {
return t;
}
f[t] = dfs(f[t]);//这是一个路径压缩，每一次遇到的节点的boss都改成最后的哪一个，节省了时间
return f[t];
}
//找到boss并返回boss的值
void follow(int u, int v) {
int b1 = dfs(u);//找节点的跟，也就是它所处的并查集，俗称找自己的boss
int b2 = dfs(v);
if (b1 != b2) {
f[b2] = b1;
}
return;
}
//合并函数
void cinit() {
for (int i = 1; i <= m; i++) {
cin >> x >> y;
follow(x, y);//将x，y归为一个并查集
}
}
//读入数据
int main() {
ios::sync_with_stdio(false);
int j = 1;//j用来记输入的第j种数据
while (1) {
int sum = 0;//sum记有多少个并查集
cin >> n >> m;//读入
if (n == 0 && m == 0) break;//题目要求 0 0时结束程序
inti();//初始化
cinit();//读入函数，
for (int i = 1; i <= n; i++) {
if (f[i] == i) sum++;//计数
}
cout << "Case " << j << ": " << sum << endl;//输出
j++;
}
return 0;
}
谢谢，别忘了这个👍!!!
网友评论