图论-并查集

问题类型

在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
这时我们就需要用到并查集了。

解决方案

在并查集中，我们要支持Union(合并)和Find(查找)操作。其中Union就是把x和y所在集合合并，Find就是查找x所在集合的代表元素。
我们在并查集中记录Fa数组，我们每次Find只要一直向上找父亲就可以了。Union只要找到x的祖先和y的祖先，然后令Fa[x] = y 就行了。

我们对并查集有两个优化：
1: 按秩合并
我们引出秩的概念，我们用秩的相对大小来表示树的相对大小（实际上就是高度）
因为我们想通过让树的深度尽量小来优化时间复杂度，所以我们合并的时候把秩小的合并到秩大的。
2: 路径压缩
我们每次都要查询一个点的祖先，而每次向上查找显然是不优的。
所以我们每次查询的同时，直接把Fa[x]改为x的祖先。

代码演示

struct UnionFindSet
{
    int Fa[N + 5], Rank[N + 5];
    void Make_Set(int x)
    {
        Fa[x] = x, Rank[x] = 0;
    }
    int Find(int x)
    {
        return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);
    }
    void Union(int x, int y)
    {
        int fx = Find(x), fy = Find(y);
        if (fx == fy) return;
        if (Rank[fx] < Rank[fy]) Fa[fx] = fy;
        else Fa[fy] = fx;
        if (Rank[fx] == Rank[fy]) Rank[fx]++;
    }
}UFS;