Graphs - 4

Covered in this section:

• Disjoint Set Union (DSU)

Disjoint Set Union (DSU)

Disjoint sets are sets that do not share any elements. They are commonly used in algorithms to keep track of connected components in a graph or to determine if two elements belong to the same set efficiently. The basic idea behind DSU is to ensure that each set is represented by only one unique item, often called the "representative" or "leader" of the set. This is achieved using two main operations:

• Find: Determines the representative of the set containing a particular element.
• Union: Merges two sets into one by connecting their representatives.

To perform DSU, we store two indices:

• Parent element: Initially, every element is its own parent, so p[i] = i. If item i is the representative of the set containing element j, then p[j] = i.
• Rank of each tree: Helps keep the height of the tree shorter. Initially, all nodes have a rank of 0, which changes as we join nodes. This will be implemented later in union operation.

Find Set Operation

The Find operation returns the representative element of a set. It uses path compression to set the parent element of a disjoint set to a distinct parent value. If two elements have the same index, they belong to the same set.

        // Find which set an element belongs to
        int findset(int index) {
            if (parent[index] == index) return index;
            return parent[index] = findset(parent[index]); // Path compression
        }
    

Union Set Operation

This operation is used to merge two disjoint sets into one. unionset(i, j) will cause set with element i and set with element j to merge. To make resulting tree as short as possible, we now use the information contained in rank vector, and ensure that rank[parent of i] <= rank[parent of j] and merge i into j.

        //union by rank, initialize rank to 0.
        void unionset(int i, int j){
            if(findset(i) == findset(j)) return;
            int x = findset(i), y = findset(j);
            if(rank[x] > rank[y])
            {
                swap(x,y);
            }
            p[x] = y;
            if(rank[x] == rank[y]) rank[y]++;
        }

        //union by size, initialize size to one
        void unionset(int i, int j){
            int x = findset(i), y = findset(j);
            if(x == y) return;
            if(size[x]> size[y])
            {
                swap(x,y);
            }
            p[x] = y;
            size[y] += size[x];
        }