定义
并查集是一种维护集合的数据结构，它的名字中”并“ ” 查“ ”集“ 分别取自 Union（合并）、Find（查找）、Set（集合）这三个单词。并查集支持下面两个操作：
- 合并：合并两个集合
- 查找：判断两个元素是否在一个集合
并查集其实是用一个数组实现的
int father[N];
father[i]表示元素i的父亲结点，而父亲结点本身也是这个集合内的元素。例如father[1] = 2表示元素1的父亲结点是元素2，以这种父亲关系来表示元素所属的集合。另外，如果father[i] = i，则说明元素i是该集合的根结点。
father[1] = 1; //1的父亲结点是自己，也就是说1号是根结点
father[2] = 1; //2的父亲结点是1
father[3] = 2; //3的父亲结点是2
father[4] = 2; //4的父亲结点是2
father[5] = 5; //5的父亲结点是自己，也就是说5号是根结点
father[6] = 6; //6的父亲结点是5
1、2、3、4在一个集合，5、6在另一个集合，是两个不同的集合。
基本操作
并查集的使用需要先初始化father数组，然后再根据需要进行查找或合并的操作
- 初始化
一开始，每个元素都是一个集合，因此需要令所有father[i]等于i
for(int i = 1; i <= N; i++) {
father[i] = i;
}
- 查找
由于规定同一个集合中只存在一个根结点，因此查找操作就是对给定的结点寻找其根结点的过程。实现方式可以是递归也可是递推。
递推：
int findFather(int x) {
while(x != father[x]) { //如果不是根结点，继续循环
x = father[x]; //获得自己的父亲结点
}
return x;
}
递归：
int findFather(int x) {
if(father[x] = x) return x;
else return findFather(father[x]);
}
- 合并
合并是指把两个集合合并成一个集合，题目中一般给出两个元素，要求把这两个元素所在的集合合并。
1 对于给定的两个元素a、b，判断它们是否属于同一集合。可以调用上面的查找函数，对这两个元素a、b分别查找根结点，然后判断其根结点是否相同。
2 合并两个集合：在上步中已经获得了两个元素的根结点faA与faB，因此只需要把其中一个的父亲结点指向另一个结点。例如 可以令father[faA] = faB，当然反过来令father[faB] = faA也是可以的
void Union(int a, int b) {
int faA = findFather(a); //查找a的根结点，记为faA
int faB = findFather(b); //查找b的根结点，记为faB
if(faA != faB) {
father[faA] = faB;
}
}
性质：在合并过程中，只对两个不同的集合进行合并，如果两个元素在相同的集合中，那么就不会对它们进行操作。这就保证了在同一个集合中一定不会产生环，即并查集产生的每一个集合都是一棵树
路径压缩
题目给出的元素数量很多并且形成一条链，那么这个查找函数的效率会非常低。
优化方法：把当前查询结点的路径上的所有结点的父亲都指向根结点，查找的时候就不需要一直回溯去找父亲了
转换过程：
- 按原先的写法获得x的根结点r
- 重新从x开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点r
递推:
int findFather(int x) {
int a = x;
while(x != father[x]) { //寻找父结点
x = father[x];
}
//到这里，x存放的是根结点。下面把路径上所有的结点都改成根结点
while(a != father[a]) {
int z = a; //因为a要被father[a]覆盖，先保存
a = father[a]; //a回溯父亲结点
father[z] = x; //将原先的结点a的父亲改为根结点x
}
return x; //返回根结点
}
递归：
int findFather(int v) {
if(v == father[v]) return v; //找到根结点
else {
int F = findFather(father[v]); //递归寻找father的根结点F
father[v] = F; //将根结点F赋给father[v]
return F;
}
}
问题描述
有一个叫做“数码世界”奇异空间，在数码世界里生活着许许多多的数码宝贝，其中有些数码宝贝之间可能是好朋友，并且数码宝贝世界有两条不成文的规定：
第一，数码宝贝A和数码宝贝B是好朋友等价于数码宝贝B与数码宝贝A是好朋友
第二，如果数码宝贝A和数码宝贝C是好朋友，而数码宝贝B和数码宝贝C也是好朋友，那么A和B也是好朋友，现在给出这些数码宝贝中所有好朋友的信息，问：可以把这些数码宝贝分成多少组，满足每组中的任意两个数码宝贝都是好朋友，而且任意两组之间的数码宝贝都不是好朋友
输入格式
输入的第一行给右两个正整数n(n<=100)和m(m<=100)，分别表示数码宝贝的个数和好朋友的组数，其中数码宝贝编号为1~n。
接下来有m行，每行两个正整数a和b，表示数码宝贝a和数码宝贝b是好朋友。
输出格式
输出一个整数，表示这些数码宝贝可以分成的组数
样例输入1
4 2
1 4
2 3
样例输出1
2
样例输入1
7 5
1 2
2 3
3 1
1 4
5 6
样例输出1
3
对同一个集合来说只存在一个根结点，且将其作为所属集合的标识
#include<cstdio>
using namespace std;
const int N = 110;
int father[N]; //存放父亲结点
bool isRoot[N]; //记录每个结点是否作为某个集合的根结点
int findFather(int x) {
int a = x;
while(x != father[x]) {
x = father[x];
}
//路径压缩（可不写）
while(a != father[a]) {
int z = a;
a = father[a];
father[z] = x;
}
return x;
}
void Union(int a, int b) {
int faA = findFather(a);
int faB = findFather(b);
if(faA != faB) {
father[faA] = faB;
}
}
void init(int n) { //初始化father[i]为i，且flag[i]为false
for(int i = 1; i <= n; i++) {
father[i] = i;
isRoot[i] = false;
}
}
int main() {
int n, m, a, b;
scanf("%d%d", &n, &m);
init(n);
for(int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
Union(a, b);
}
for(int i = 1; i <= n; i++) {
isRoot[findFather(i)] = true; //i的根结点是findFather[i]
}
int ans = 0;//记录集合的数目
for(int i = 1; i <= n; i++) {
ans += isRoot[i];
}
printf("%d\n", ans);
return 0;
}
