并查数据结构

该博客上撰写的文章是出于教学目的而创建的。 另外，文章中的信息可能不正确，请谨慎。

并查（Union-Find）是一种快速检查多个元素是否属于同一集合并将两个集合组合起来的数据结构。 不相交集并集，也简称为DSU。

寻找家长代表

class DisjointSet
{
public:
    explicit DisjointSet(int Count)
        : Parent(Count), Rank(Count, 0)
    {
        std::iota(Parent.begin(), Parent.end(), 0);
    }

    int Find(int Value)
    {
        if (Parent[Value] != Value)
        {
            Parent[Value] = Find(Parent[Value]);
        }

        return Parent[Value];
    }

    bool Unite(int A, int B)
    {
        A = Find(A);
        B = Find(B);

        if (A == B)
        {
            return false;
        }

        if (Rank[A] < Rank[B])
        {
            std::swap(A, B);
        }

        Parent[B] = A;

        if (Rank[A] == Rank[B])
        {
            ++Rank[A];
        }

        return true;
    }

private:
    std::vector<int> Parent;
    std::vector<int> Rank;
};

路径压缩在查找过程中将父级直接连接到代表。 按等级并集通过将较低的树附加到较高的树下来防止深度增加。

当两种优化一起使用时，操作实际上在几乎恒定的时间内运行。

它用在哪里？

• 检查两个区域是否连通。
• 检查添加边沿时是否出现循环。
• 使用 Kruskal 算法创建最小生成树。
• 继续在线组合组合。

Union-Find 本身不提供路径。 当目的是连接或集合合并时，它是一个强大的数据结构。