并查集是什么

并查集是用来管理元素分组的算法。

并查集的实现

并查集的优化

不作优化的并查集的时间复杂度是O(log(n))，并且有可能退化成一条链，这时时间复杂度高达O(n)，显然是不行的。
因此，我们还有两种优化方式：

按秩合并（避免退化）

按秩合并指将高度较小的树连接到高度较高的树的根上，意味着我们需要增加一个h（height）数组记录树的高度。

路径压缩

我们在查询时，一层一层向根查询，如果能够将每个节点的父节点都变成根节点多好啊。
我们可以在查询时，将查询路径上的每个节点的父节点都赋值成根节点。

模板代码

void Init() {
    for(int i=0; i<=n; i++) {
        f[i] = i;
        h[i] = 0;
    }
}
int Find(int i) {
    return f[i]==i ? f[i] : f[i]=Find(f[i]);
}
void merge(int a, int b) {
    int fa = Find(a);
    int fb = Find(b);
    if(fa != fb) {
        if(h[fa] < h[fb]) {
            f[fa] = fb;
        } else {
            f[fb] = fa;
            if(h[fa] == h[fb]) h[fa]++;
        }
    }
}