並查資料結構

該部落格上撰寫的文章是出於教學目的而創建的。 另外，文章中的資訊可能不正確，請謹慎。

並查（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 本身不提供路徑。 當目的是連接或集合合併時，它是一個強大的資料結構。