并查集是一类算法的总称，也可以说是一种数据结构。它其实是由三个部分组成的:
- 并：合并两点所在的集合
- 查：查询某点所在的集合
- 集：集合
这三种操作是并查集最重要的部分。
其实并查集本质上是一个树林，也就相当于说它的每一个集合都是一颗树。
怎么存呢？
我们用一个数组fa[i]来表示节点i的父亲.
如果i节点没有父亲，fa[i] = i.
接下来我就开始讲讲如何实现了。
三种操作中最基本的就是查询了。
其想法是从该点出发进行递归，
每一次先判断fa[i]是否等于i
如果等于i就return i，
不等于的话就问i的father
直接上代码（C++）
int get(int x) {
if (x == fa[x]) return x;
return get(fa[x]);
}
虽然听起来起来很高大上，但是代码就4行，想记不下来都难 ^_^
时间复杂度： O(1)~O(n) (n是该树的大小)
注：get(i) 返回的是i的根结点，根结点就代表整棵树
然后便是合并
合并是基于查询的，
其实就是先把两个点的根结点get出来
然后先康一下俩节点是不是在一个集合里，
不是的话就把任意一个节点的father设为另一个节点
代码来喽：
void merge(int x, int y) {
x = get(x);
y = get(y);
if (x != y) fa[y] = x;
}
合并的代码也不算多，5行，对于你们这些大佬肯定是小case的。
时间复杂度： O(1)~O(n) (n是该树的大小)
划重点！
并查集有两种优化方法，且互不干扰
如果两种都用上可以把两个操作的时间复杂度压到O(1)！
No.1 路径压缩
路径压缩原理很简单，就是如果你查询的一个节点x，查到了根节点后把x的father设为x的根节点，
独自使用的话可以把时间复杂度压到O(logn)(n为树的大小)
只要把get改一改就行啦。
代码：
int get(int x) {
if (x == fa[x]) return x;
fa[x] = get(fa[x]);
return fa[x];
}
路径压缩是并查集最常用，也是最简单的优化方式。
No.2 按秩合并
顾名思义，按秩合并就是按照秩序合并。
具体怎么按照秩序呢？
其实就是在合并时判断一下，把深度较小的树合并到深度较大的树中去
上代码！
int dep[maxn]; // 储存深度
void merge(int x, int y) {
x = get(x);
y = get(y);
int fx = dep[x]; // 表示x树的大小
int fy = dep[y]; // 表示y树的大小
if (fx < fy) {
fa[x] = y;
} else if (fx == fy) {
fa[x] = y;
dep[y]++;
else {
fa[y] = x;
}
}
忘记说了
初始化时要记得把fa[i]设成i， dep[i]设成1哦!
最后发下全部代码
int fa[maxn];
int dep[maxn]; // 储存深度
int get(int x) {
if (x == fa[x]) return x;
fa[x] = get(fa[x]);
return fa[x];
}
void merge(int x, int y) {
x = get(x);
y = get(y);
int fx = dep[x]; // 表示x树的大小
int fy = dep[y]; // 表示y树的大小
if (fx < fy) {
fa[x] = y;
} else if (fx == fy) {
fa[x] = y;
dep[y]++;
else {
fa[y] = x;
}
}
总结：
并查集是一个在竞赛与程序中都很常见的算法，大家一定要牢牢掌握它哦。
