Disjoint Set Union: Efficiently Managing Connected Components

Disjoint Set Union (DSU), also called Union-Find, is a specialized data structure for maintaining a collection of non-overlapping sets. It efficiently determines whether two elements belong to the same group and merges groups when required.

DSU is especially useful when relationships between elements are added dynamically. Instead of repeatedly traversing a graph to determine connectivity, DSU maintains representative information that allows connectivity checks and set merges to be performed extremely efficiently.

The two fundamental operations are find, which identifies the representative of an element's set, and union, which combines two different sets into one. With path compression and union by rank or size, these operations have an amortized complexity of O(alpha(N)), where alpha is the inverse Ackermann function and grows so slowly that it is effectively constant for practical input sizes.

Structure and Parent Array Representation

A DSU represents every set as a rooted tree. Each element stores a parent reference, and the root of a tree acts as the representative of the entire set.

• Parent Array: parent[i] stores the immediate parent of element i.
• Root Node: A root is an element whose parent points to itself.
• Representative: The root uniquely identifies the set containing an element.
• Rank or Size: Additional metadata can be stored to keep trees shallow during union operations.
• Independent Sets: Initially, every element belongs to its own separate set.

For N elements, the parent array requires O(N) memory. A second array can maintain either the rank or the size of each component to guide efficient merging.

Core Operations and Complexity

1. Make Set

Initially, every element forms an independent set. Therefore, parent[i] is initialized to i, meaning each element is its own representative.

Creating N independent sets requires O(N) initialization time.

2. Find

The find operation follows parent pointers until it reaches a root. The root is the representative of the set containing the queried element.

Path compression optimizes this process by making every node encountered during the traversal point directly to the root. Future find operations on those nodes therefore become significantly faster.

3. Union

The union operation combines the sets containing two elements. First, find is called for both elements to identify their representatives. If the representatives are different, the two sets can be merged.

Union by rank attaches the shorter tree beneath the taller tree, while union by size attaches the smaller component beneath the larger component. Both strategies prevent the DSU trees from becoming unnecessarily deep.

Path Compression: Flattening the Tree

Without optimization, repeated union operations can create long chains of parent pointers. A find operation may then require traversing many nodes before reaching the root.

Path compression solves this problem by directly connecting every node visited during find to the root. The next time those elements are queried, the traversal becomes much shorter.

1. Start from the requested element.
2. Follow parent pointers until the root representative is found.
3. During the recursive return, update each visited node's parent to the root.
4. Future find operations can then reach the representative in significantly fewer steps.

When combined with union by rank or union by size, path compression gives DSU its well-known near-constant amortized performance.

Union by Rank and Union by Size

Union by Rank

Each set maintains an approximate measure of its tree height called rank. When merging two sets, the root with smaller rank is attached below the root with larger rank. If both ranks are equal, one root becomes the parent and its rank is increased.

Union by Size

Instead of tracking tree height, union by size stores the number of elements in each component. The smaller component is attached beneath the larger component.

Both approaches are effective. Union by size is particularly useful when applications also need to know the number of elements contained in each connected component.

C++ Implementation Blueprint

class DSU {
private:
    std::vector<int> parent;
    std::vector<int> size;

public:
    DSU(int n) {
        parent.resize(n);
        size.assign(n, 1);

        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] == x)
            return x;

        return parent[x] = find(parent[x]);
    }

    bool unite(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB)
            return false;

        if (size[rootA] < size[rootB])
            std::swap(rootA, rootB);

        parent[rootB] = rootA;
        size[rootA] += size[rootB];

        return true;
    }

    bool connected(int a, int b) {
        return find(a) == find(b);
    }
};

Time and Space Complexity

The performance of DSU depends heavily on its balancing optimizations. A naive implementation can produce tall trees, but path compression combined with union by rank or size provides extremely efficient amortized performance.

• Make Set: O(N) for initializing N elements.
• Find: O(alpha(N)) amortized with path compression and union by rank or size.
• Union: O(alpha(N)) amortized when implemented with the same optimizations.
• Connectivity Check: O(alpha(N)) amortized because it performs two find operations.
• Space Complexity: O(N) for parent and auxiliary rank or size arrays.

The inverse Ackermann function alpha(N) grows extraordinarily slowly. For all realistic computational input sizes, it remains a very small constant, which makes optimized DSU effectively constant time per operation in practice.

Cycle Detection in Undirected Graphs

DSU can detect cycles while processing the edges of an undirected graph. For every edge connecting vertices u and v, check whether both vertices already belong to the same set.

1. Initialize every vertex as a separate set.
2. Process each graph edge (u, v).
3. Find the representatives of u and v.
4. If both representatives are identical, adding the edge creates a cycle.
5. Otherwise, unite the two components.

This technique is particularly effective when edges are processed incrementally and only connectivity information is required.

DSU in Kruskal's Minimum Spanning Tree Algorithm

One of the most important applications of DSU is Kruskal's algorithm for finding a Minimum Spanning Tree (MST). DSU efficiently determines whether adding an edge would connect two already-connected vertices and therefore create a cycle.

1. Sort all graph edges by increasing weight.
2. Initialize a DSU containing every vertex as a separate component.
3. Process edges from smallest to largest weight.
4. Use find to determine whether the edge's endpoints belong to different components.
5. If they are different, add the edge to the MST and unite the two components.
6. Continue until the MST contains N - 1 edges.

The DSU operations make the connectivity checks extremely efficient, allowing Kruskal's algorithm to focus primarily on sorting the graph edges.

Real-World and Algorithmic Applications

• Network Connectivity: Maintaining dynamically connected groups of computers, servers, or communication nodes.
• Kruskal's Algorithm: Efficiently constructing minimum spanning trees in weighted graphs.
• Image Processing: Identifying connected regions and components in binary images.
• Social Networks: Maintaining groups or communities as relationships are progressively added.
• Dynamic Connectivity: Determining whether two objects remain connected after a sequence of relationship additions.
• Clustering: Managing and merging groups of related data points during hierarchical or connectivity-based clustering.
• Competitive Programming: Solving component-merging, cycle-detection, MST, and offline connectivity problems.

When Should You Use DSU?

DSU is ideal when elements begin in separate groups and the primary operations involve merging groups and checking whether two elements belong to the same component.

• Use DSU when connected components are repeatedly merged.
• Use DSU when connectivity checks must be extremely fast.
• Use DSU for cycle detection in undirected graphs.
• Use DSU as a core component of Kruskal's MST algorithm.
• Use union by size when component sizes need to be tracked.
• Prefer graph traversal algorithms such as BFS or DFS when components need to be explored rather than simply identified.