Union-Find data structure

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

Union-Find is a data structure that quickly checks whether multiple elements belong to the same set and combines two sets. Disjoint Set Union, also called DSU for short.

Search for a representative as a 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 connects the parent directly to the representative during the Find process. Union by Rank prevents depth from increasing by attaching a lower tree under a higher tree.

When both optimizations are used together, the operation actually behaves in almost constant time.

Where is it used?

• Check whether the two regions are connected.
• Check whether a cycle occurs when an edge is added.
• Create a minimum spanning tree using the Kruskal algorithm.
• Continue combining sets online.

Union-Find does not provide the path itself. It is a powerful data structure when the purpose is connection or set merging.