Union by Rank and Path Compression

To optimize the naive Disjoint Set operations, we can apply two key techniques: Union by Rank and Path Compression. Combining these reduces the amortized time complexity of operations to nearly constant time O(1).

1. Union by Rank

In the naive Union operation, we always attach the first tree under the second tree. If we insert elements sequentially, the tree can become a single linear chain of height N, leading to O(N) find times.

Union by Rank avoids this:

We maintain a rank array storing the height/depth of each tree.
During a Union operation, we attach the root of the tree with the smaller rank to the root of the tree with the larger rank.
If the ranks are equal, we can pick either as parent and increment its rank by 1.

2. Path Compression

During a find operation, we traverse up to find the root representative.

Path Compression flattens the tree structure:

After finding the root, we update the parent pointer of every visited node along the path to point directly to the root.
The next time find is called for any node in that path, the lookup completes in O(1) time.

JavaScript Implementation (Cycle Detection with Optimizations)

Here is how to implement the optimized Disjoint Set data structure to detect a cycle in a graph:

class DisjointSet {
    constructor(n) {
        this.parent = new Array(n).fill(-1);
        this.rank = new Array(n).fill(0);
    }
 
    // Find operation with Path Compression
    find(i) {
        if (this.parent[i] === -1) {
            return i;
        }
        // Path compression: cache the root parent directly
        this.parent[i] = this.find(this.parent[i]);
        return this.parent[i];
    }
 
    // Union operation by Rank
    union(x, y) {
        let xRoot = this.find(x);
        let yRoot = this.find(y);
 
        if (xRoot !== yRoot) {
            // Attach smaller rank tree under root of high rank tree
            if (this.rank[xRoot] < this.rank[yRoot]) {
                this.parent[xRoot] = yRoot;
            } else if (this.rank[xRoot] > this.rank[yRoot]) {
                this.parent[yRoot] = xRoot;
            } else {
                // If ranks are same, make one as root and increment its rank
                this.parent[yRoot] = xRoot;
                this.rank[xRoot]++;
            }
            return true; // Union successful
        }
 
        return false; // Already in the same set
    }
}
 
function hasCycle(vertices, edges) {
    const ds = new DisjointSet(vertices);
 
    for (let i = 0; i < edges.length; i++) {
        let u = edges[i][0];
        let v = edges[i][1];
 
        // Find roots of both vertices
        let rootU = ds.find(u);
        let rootV = ds.find(v);
 
        // If roots are the same, u and v are already connected -> Cycle found
        if (rootU === rootV) {
            return true;
        }
 
        ds.union(rootU, rootV);
    }
 
    return false;
}
 
// Driver code
const vertices = 4;
const edges = [
    [0, 1],
    [1, 2],
    [2, 3],
    [3, 0]
];
 
if (hasCycle(vertices, edges)) {
    console.log("Graph contains cycle");
} else {
    console.log("Graph doesn't contain cycle");
}
// Output: Graph contains cycle

Complexity Analysis

Time Complexity:
- Amortized Time: O(alpha(N)) for both find and union operations, where alpha is the Inverse Ackermann function. This function grows extremely slowly, so the operations are effectively O(1) for all practical values of N.
Space Complexity: O(N)
- For storing the parent and rank arrays.

Introduction to Disjoint Set Kruskal's MST Algorithm