目录
概述
并查集，故名思议，能合并、能查询的集合,在图的连通性问题和许多算法优化上着广泛的使用。
这是一个什么数据结构呢？
一般来讲，并查集是由一系列集合组成的集合群。
其中，每个集合都有一个根节点，它的父亲仍是它自己，集合内其余的节点的父亲or祖宗均是这个节点，这样，一个根节点就领导了一个集合。而并查集支持这样的多个集合的访问以及合并操作。
每个集合都是一个树形结构，你可以认为并查集是一片森林。
听起来挺复杂度，但是其实很好实现。
成员变量
static constexpr int N = 1e5 + 5;一个无关紧要的常量，限制最大值。
int pre[N];父节点指针数组,pre[i]=j表示i的父亲是j，即二者处于同一集合。
int size[N];集合大小数组，只用每个集合的根节点上的size是有意义的，若i为根节点size[i]=x表示i所在的集合大小为x。
struct union_find_set {
static constexpr int N = 1e5 + 5;
int pre[N],size[N];
...
};创建销毁
在一开始，每个节点都单独成为一个集合，每个集合大小为1。
union_find_set(int n = N) {
for (int i = 0; i < n; i++) {
pre[i] = i;
size[i] = 1;
}
}根节点访问
给定一个节点x，我们想访问他的根节点。
这一步可以递归实现：我们知道只有根节点的pre指向自己，所以如果pre[x]==x，我们就找到了根节点，否则沿着pre指针爬，传入下一级root。
int root(int x) {
return pre[x] == x ? x : root(pre[x]);
}路径压缩
沿着pre指针爬树的过程的时间复杂度是线性级别的，但是我们可以使用路径压缩：
当我们依次跳出递归时，额外将这一级x的pre指针更新为找到的根节点，这样，一棵树就由多层被压缩成了两层（根节点与叶子节点）。
int root(int x) {
return pre[x] = (pre[x] == x ? x : root(pre[x]));
}启发式合并
想合并两个集合，我们可以采用启发式合并，即按规模合并。
路径压缩并不是实时的，所以一般一个集合仍是多层的。在这种情况下，为了保持查询根节点的高效性，我们应该将小集合接在大集合之下（小集合中节点少，向上访问的总代价小，如果反过来，那么大集合中的大量节点想向上访问会极其不利）。
给出两个节点，将其所在的集合合并，我们先找出root，如果两个节点确实属于不同集合，我们将小集合接在大集合之下，这样就能保持根节点查询的效率。最后根节点的size。
void unite(int x, int y) {
x = root(x), y = root(y);
if (x == y)return;
if (size[y] < size[x])std::swap(x, y);
pre[x] = y;
size[y] += size[x];
}复杂度
时间复杂度：O(n) 使用路径压缩：O(1)~O(logn)
空间复杂度：O(n)
Code
#include <algorithm>
#ifndef UNION_FIND_SET
#define UNION_FIND_SET
struct union_find_set {
static constexpr int N = 1e5 + 5;
int pre[N],size[N];
union_find_set(int n) {
for (int i = 0; i < n; i++) {
pre[i] = i;
size[i] = 1;
}
}
int root(int x) {
return pre[x] = (pre[x] == x ? x : root(pre[x]));
}
int get_size(int x) {
return size[root(x)];
}
void unite(int x, int y) {
x = root(x), y = root(y);
if (x == y)return;
if (size[y] < size[x])std::swap(x, y);
pre[x] = y;
size[y] += size[x];
}
};
#endif