Union-Find (Disjoint Set Union) — The Connectivity Powerhouse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Let's understand just how slowly α(n) grows:
 
n          | α(n)
───────────┼──────
1-2        | 0
3          | 1
4-7        | 2
8-61       | 3
62 - 2^65536 | 4
 
To get α(n) = 5, we need n > 2^65536
 
How big is 2^65536?
- 2^10 ≈ 1,000 (thousand)
- 2^20 ≈ 1,000,000 (million)
- 2^30 ≈ 1,000,000,000 (billion)
- 2^100 ≈ 10^30 (far more than atoms in a human body)
- 2^256 ≈ 10^77 (more than atoms in the observable universe)
- 2^65536 ≈ 10^19,000
 
That's a number with ~20,000 digits.
 
There's no computer that could store this many elements.
There aren't this many particles in existence.
 
Therefore, for ANY real program: α(n) ≤ 4
 
This is why we say α(n) is "effectively constant."

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Consider an edge from node v to its parent p.
 
When is this edge traversed during Find?
→ Only when a Find path passes through v.
 
What happens during path compression?
→ v gets a new parent (closer to or at the root)
 
After compression, the old edge v→p is never traversed again!
v now points somewhere higher, bypassing p entirely.
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Accounting insight:
 
"Charge" each edge traversal to either:
1. The Find operation itself (limited per Find), or
2. The node being improved (limited per node)
 
Each node can only be "improved" a limited number of times.
How limited? This is where rank groups and the inverse 
Ackermann function enter...
 
The analysis divides ranks into O(α(n)) "blocks."
Each node can move between blocks at most O(1) times.
Therefore, total work is O(m + n × α(n)) = O(m × α(n)) for m ≥ n.
 
Per-operation amortized cost: O(α(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * Benchmark comparing naive vs optimized Union-Find.
 */
function benchmarkUnionFind(n: number, operations: number) {
    console.log(`Benchmarking with n=${n}, operations=${operations}`);
    
    // Optimized version
    const optimized = new UnionFind(n);  // With rank + path compression
    
    const startOptimized = performance.now();
    for (let i = 0; i < operations; i++) {
        const a = Math.floor(Math.random() * n);
        const b = Math.floor(Math.random() * n);
        if (i % 2 === 0) {
            optimized.union(a, b);
        } else {
            optimized.connected(a, b);
        }
    }
    const endOptimized = performance.now();
    
    console.log(`Optimized: ${(endOptimized - startOptimized).toFixed(2)}ms`);
    console.log(`Operations per ms: ${(operations / (endOptimized - startOptimized)).toFixed(0)}`);
}
 
// Typical results on modern hardware:
// n = 1,000,000, operations = 10,000,000
// Optimized: ~200-500ms
// That's 20,000-50,000 operations per millisecond!
 
// Compare to naive O(n) per operation:
// 10,000,000 * ~500 average hops = ~5,000,000,000 operations
// Would take minutes instead of milliseconds

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

/**
 * Union-Find (Disjoint Set Union) with Path Compression + Union by Rank
 * 
 * The optimal Union-Find implementation achieving O(α(n)) amortized time
 * per operation, where α is the inverse Ackermann function.
 * 
 * For all practical purposes: O(1) amortized per operation.
 * 
 * Features:
 * - Path compression (path halving variant)
 * - Union by rank for balanced trees
 * - Set count tracking
 * - Set size queries
 * - Validation and error handling
 * 
 * @example
 * const uf = new UnionFind(10);
 * uf.union(0, 1);
 * uf.union(2, 3);
 * console.log(uf.connected(0, 1));  // true
 * console.log(uf.connected(0, 2));  // false
 * console.log(uf.getCount());       // 8
 */
class UnionFind {
    private readonly parent: number[];
    private readonly rank: number[];
    private readonly size: number[];
    private count: number;
    
    /**
     * Create a Union-Find structure with n elements (0 to n-1).
     * Initially, each element is in its own singleton set.
     * 
     * Time: O(n)
     * Space: O(n)
     */
    constructor(n: number) {
        if (!Number.isInteger(n) || n <= 0) {
            throw new Error(`Invalid size: ${n}. Must be a positive integer.`);
        }
        
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.size = new Array(n).fill(1);
        this.count = n;
    }
    
    /**
     * Find the representative (root) of the set containing x.
     * Uses path halving for compression.
     * 
     * Time: O(α(n)) amortized ≈ O(1)
     */
    find(x: number): number {
        this.validate(x);
        
        while (this.parent[x] !== x) {
            // Path halving: each node points to its grandparent
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }
    
    /**
     * Merge the sets containing x and y.
     * Uses union by rank to keep trees balanced.
     * 
     * Time: O(α(n)) amortized ≈ O(1)
     * @returns true if a merge occurred, false if already in same set
     */
    union(x: number, y: number): boolean {
        const rootX = this.find(x);
        const rootY = this.find(y);
        
        if (rootX === rootY) {
            return false;  // Already connected
        }
        
        // Union by rank
        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
            this.size[rootY] += this.size[rootX];
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
            this.size[rootX] += this.size[rootY];
        } else {
            this.parent[rootY] = rootX;
            this.size[rootX] += this.size[rootY];
            this.rank[rootX]++;
        }
        
        this.count--;
        return true;
    }
    
    /**
     * Check if x and y are in the same set.
     * 
     * Time: O(α(n)) amortized ≈ O(1)
     */
    connected(x: number, y: number): boolean {
        return this.find(x) === this.find(y);
    }
    
    /**
     * Get the number of disjoint sets.
     * 
     * Time: O(1)
     */
    getCount(): number {
        return this.count;
    }
    
    /**
     * Get the size of the set containing x.
     * 
     * Time: O(α(n)) amortized ≈ O(1)
     */
    getSize(x: number): number {
        return this.size[this.find(x)];
    }
    
    /**
     * Get the total number of elements.
     * 
     * Time: O(1)
     */
    getElementCount(): number {
        return this.parent.length;
    }
    
    /**
     * Check if all elements are in the same set.
     * 
     * Time: O(1)
     */
    isFullyConnected(): boolean {
        return this.count === 1;
    }
    
    private validate(x: number): void {
        if (!Number.isInteger(x) || x < 0 || x >= this.parent.length) {
            throw new RangeError(
                `Index ${x} out of bounds. Valid range: [0, ${this.parent.length - 1}]`
            );
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Count connected components in an undirected graph.
 * 
 * @param n - Number of nodes (0 to n-1)
 * @param edges - Array of [u, v] pairs representing edges
 * @returns Number of connected components
 * 
 * Time: O(n + E·α(n)) ≈ O(n + E)
 */
function countComponents(n: number, edges: number[][]): number {
    const uf = new UnionFind(n);
    
    for (const [u, v] of edges) {
        uf.union(u, v);
    }
    
    return uf.getCount();
}
 
// Example:
// n = 5, edges = [[0,1], [1,2], [3,4]]
// Result: 2 components ({0,1,2} and {3,4})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 * Detect if an undirected graph contains a cycle.
 * 
 * Key insight: A cycle exists if we try to add an edge
 * between two vertices that are already connected.
 * 
 * Time: O(E·α(V)) ≈ O(E)
 */
function hasCycle(n: number, edges: number[][]): boolean {
    const uf = new UnionFind(n);
    
    for (const [u, v] of edges) {
        // If u and v are already connected, adding this edge creates a cycle
        if (uf.connected(u, v)) {
            return true;
        }
        uf.union(u, v);
    }
    
    return false;
}
 
// Example:
// n = 4, edges = [[0,1], [1,2], [2,0]]
// On edge [2,0]: connected(2, 0) is true → cycle detected!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 * Find the earliest timestamp when all people are connected.
 * 
 * logs[i] = [timestamp, person_a, person_b] means a and b 
 * became friends at that timestamp.
 * 
 * Time: O(L log L + L·α(n)) where L = number of logs
 */
function earliestAcq(logs: number[][], n: number): number {
    // Sort by timestamp
    logs.sort((a, b) => a[0] - b[0]);
    
    const uf = new UnionFind(n);
    
    for (const [timestamp, a, b] of logs) {
        uf.union(a, b);
        
        // When count reaches 1, everyone is connected
        if (uf.getCount() === 1) {
            return timestamp;
        }
    }
    
    return -1;  // Never fully connected
}