如果用连续的整数对元素进行编号。比如有N个元素，则依次分配ID为 0,1,2...N-1。
为了方便实现，我们将 【根节点的ID】作为【集合的ID】，见下方init()接口。
1.并查集有merge 和 find 两个函数
find(x) ：通过 x 的父节点，父节点的父节点 ... ...，一直找到根节点并返回其ID。
merge(u,v)：通过 find 函数找到 u，v 的根节点 root_u, root_v。如果两者的根节点不相同，则将 root_u 的父节点设为 root_v。如果相同，则无需任何操作。
综上，并查集不关心节点有哪些儿子，只关心节点的父亲是谁，所以并查集只需要一个数组 int father[n];
father[i]记录节点i的父节点；特殊的，当 i 是根节点时，father[i] 的值为 i。
2.那如何快速查询两个元素是否来自同一父亲呢？
这个简单，直接比较所属集合ID是否相同即可。
// 初始时，每个节点都构成了一棵树，即每个节点都是一个根节点
int N = 1000;
void init(int N)
{
for (int i = 0; i < N; i++) { // 此处初始化，默认是使用「根节点的ID」 作为 「集合的ID」
fa[i] = i;
}
}
// 找到元素x所属的父集合id
int find(int x)
{
int r = x;
while (father[r] != r) {
r = father[r];
}
return r;
}
// 基于 find(x) 函数，实现 merge(u,v) ，很简单
void merge(int u, int v)
{
int ru = find(u);
int rv = find(v);
if (ru != rv) {
father[ru] = rv;
}
return;
}
【路径压缩】的核心思想：并查集其实也不关心节点的父亲是谁，它真正关心的是 【节点的根是谁】。既然这样，father[i] 直接记录节点 i 的根不就行了嘛。
// 第一个 while：找到 x 所在树的根节点 r
// 第二个 while：将 x → r 路径上的所有节点的 father 更新为 r
int find(int x) {
int r = x;
while(father[r] != r) {
r = father[r];
}
while(father[x] != x) { // 这里是路径压缩处理,为将来查找实现O(n)到O(1)的转变
int t = father[x];
father[x] = r;
x = t;
}
return x;
}
// 基于 find(x) 函数，实现 merge(u,v)
bool merge(int u, int v) {
int ru = find(u);
int rv = find(v);
if (ru != rv) {
father[ru] = rv;
return true;
}
return false;
}
yo peace！
