题目大意
一个学校有n(n<=50000)个学生，他们都可能信仰不同的宗教，你不能一个一个去问他们的信仰，但你可以通过询问得知两个学生的信仰是否一致，询问有m(m<=n*(n-1)/2)次。通过询问你可以知道校内学生的信仰总数上限，找到这个上限作为答案。
思路
其实就是一个并查集，题目翻译过来就是说给你一个图与它的一些边，找到所有的联通分量。
代码
#include <set>
#include <vector>
#include <cstdio>
#include <utility>
#include <iostream>
using namespace std;
const int N = 55000;
int cnt;
int n, m;
int dad[N];
void init(int top) {
for(int i = 1; i <= top; i++) {
dad[i] = i;
}
}
int get(int x) {
return dad[x] == x ? x : get(dad[x]);
}
void merge(int x, int y) {
x = get(x);
y = get(y);
if(x != y) {
dad[y] = x;
}
}
int main() {
while(scanf("%d%d", &n, &m)) {
int ans = 0;
if(n == 0 && m == 0) break;
init(n);
int a, b;
for(int i = 1; i <= m; i++) {
scanf("%d%d", &a, &b);
merge(a, b);
}
for(int i = 1; i <= n; i++) {
if(i == get(i)) {
ans++;
}
}
printf("Case %d: %d\n", ++cnt, ans);
}
return 0;
}
并查集
并查集的核心思想是记录某个节点的父节点是谁。它可以快速的判断某个节点是父节点是谁或者它属于哪个点集合(联通分量)。通常有三种操作：
初始化
初始状态每个节点的父节点就是自己。
void init(int n) {
for(int i = 1; i <= n; i++) {
father[i] = i;
}
}
查询
递归遍历整个关系树，找到当前节点的父节点。
int find(int x) {
return father[x] == x ? x : find(father[x]);
}
路径压缩
事实上，上述的查询函数在极端情况下的复杂度相当高。假设当前关系树是一条链，此时find函数的复杂度会达到O(n)。复杂度如此高的原因是每次find操作都递归到根节点才结束，而关系树真正的结构可能会无比畸形。
其实查询时我们只关注的是每个节点的父节点是谁，没人关心对于关系树真正的造型是什么样的。所以我们可以在find函数查找的同时，将路径上的每个节点的父节点都重设为根节点，这样就能做到往后每次查询的复杂度都是常数时间。
int find(int x) {
return father[x] == x ? x : father[x] = find(father[x]);
}
[图片缺失] 原图：https://img-blog.csdn.net/20180609171300274
如上图，最终关系树会变成一个海胆的造型。
合并
通过将两个节点的父节点设为同一个来合并两个元素所在的集合，合并前判断当前节点是否已经属于同一个集合。
void merge(int x, int y) {
x = get(x);
y = get(y);
if(x != y) {
father[y] = x;
}
}