【tip】并查集（路径压缩）使用小结

如果用连续的整数对元素进行编号。比如有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！