Union-Find データ構造

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

Union-Findは、複数の元素が同じ集合に属するかを素早く確認し、2組を合わせるデータ構造だ。 Disjoint Set Union、減ってDSUとも呼ぶ。

Parentで代表を探す

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;
};

Path Compression は Find の過程で親を代表に直接接続する。 Union by Rank は低い木を高い木の下に貼り付け、深さが大きくなるのを防ぐ。

両方の最適化を一緒に使用すると、演算は実際にはほぼ定数時間のように動作します。

どこに使用するか。

• 2つの地域が接続されていることを確認してください。
• トランクを追加したときにサイクルが発生するかどうかを調べます。
• Kruskalアルゴリズムで最小腎臓ツリーを作成します。
• オンラインで集合を合わせ続ける。

Union-Findはパス自体を知らせません。 連結の有無と集合併合が目的であるときの強力なデータ構造だ。