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

class UnionFind {
    private parent: number[];
    
    constructor(n: number) {
        // Each element starts as its own root
        this.parent = Array.from({ length: n }, (_, i) => i);
    }
    
    /**
     * Find the root (representative) of element x's set.
     * 
     * Time Complexity: O(d) where d is the depth of x in its tree
     * In the worst case (unbalanced tree), this is O(n)
     * 
     * @param x - The element to find the root of
     * @returns The root (representative) of x's set
     */
    find(x: number): number {
        // Traverse up the tree until we reach the root
        // Root is identified by being its own parent: parent[r] = r
        while (this.parent[x] !== x) {
            x = this.parent[x];  // Move to parent
        }
        return x;  // x is now the root
    }
    
    /**
     * Check if two elements are in the same set.
     * Simply compares their roots.
     */
    connected(x: number, y: number): boolean {
        return this.find(x) === this.find(y);
    }
}

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

Tree Structure:
                    [0] ← root
                   / | \
                 [1][2][3]
                     |
                    [4]
                     |
                    [5]
 
parent array: [0, 0, 0, 0, 2, 4]
              ↑  ↑  ↑  ↑  ↑  ↑
          idx: 0  1  2  3  4  5
 
parent[0] = 0 (root: points to itself)
parent[1] = 0 (1's parent is 0)
parent[2] = 0 (2's parent is 0)
parent[3] = 0 (3's parent is 0)
parent[4] = 2 (4's parent is 2)
parent[5] = 4 (5's parent is 4)
 
Find(5) execution trace:
─────────────────────────
Step 1: x = 5
        Is parent[5] === 5?  → parent[5] = 4 → NO
        Move to parent: x = parent[5] = 4
 
Step 2: x = 4
        Is parent[4] === 4?  → parent[4] = 2 → NO
        Move to parent: x = parent[4] = 2
 
Step 3: x = 2
        Is parent[2] === 2?  → parent[2] = 0 → NO
        Move to parent: x = parent[2] = 0
 
Step 4: x = 0
        Is parent[0] === 0?  → parent[0] = 0 → YES!
        Return 0
 
Result: Find(5) = 0
 
The path traversed: 5 → 4 → 2 → 0
Path length: 3 hops

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

class UnionFind {
    private parent: number[];
    private setCount: number;  // Track number of disjoint sets
    
    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.setCount = n;  // Initially n separate sets
    }
    
    find(x: number): number {
        while (this.parent[x] !== x) {
            x = this.parent[x];
        }
        return x;
    }
    
    /**
     * Merge the sets containing x and y.
     * 
     * Time Complexity: Dominated by two Find calls
     *   - Best case: O(1) if roots are direct
     *   - Worst case: O(n) in unbalanced trees
     * 
     * @param x - First element
     * @param y - Second element
     * @returns true if a merge occurred, false if already connected
     */
    union(x: number, y: number): boolean {
        const rootX = this.find(x);
        const rootY = this.find(y);
        
        // Already in the same set - nothing to do
        if (rootX === rootY) {
            return false;  // No merge occurred
        }
        
        // Merge: make rootY point to rootX
        // (This is an arbitrary choice - we'll optimize this later)
        this.parent[rootY] = rootX;
        
        // One less disjoint set now
        this.setCount--;
        
        return true;  // Merge occurred
    }
    
    /**
     * Get the current number of disjoint sets.
     */
    getSetCount(): number {
        return this.setCount;
    }
}

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

Before Union(3, 7):
 
Tree A:           Tree B:
  [0]               [5]
 / | \              / \
[1][2][3]         [6] [7]
    |
   [4]
 
parent: [0, 0, 0, 0, 2, 5, 5, 5]
        ↑  ↑  ↑  ↑  ↑  ↑  ↑  ↑
idx:    0  1  2  3  4  5  6  7
 
Set A = {0, 1, 2, 3, 4} with root 0
Set B = {5, 6, 7} with root 5
 
Union(3, 7) execution trace:
──────────────────────────────
 
Step 1: Find root of 3
        Find(3): 3 → parent[3] = 0 → parent[0] = 0 ✓
        rootX = 0
 
Step 2: Find root of 7
        Find(7): 7 → parent[7] = 5 → parent[5] = 5 ✓
        rootY = 5
 
Step 3: Compare roots
        rootX (0) ≠ rootY (5)
        Different sets - proceed with merge
 
Step 4: Merge
        parent[rootY] = rootX
        parent[5] = 0
 
After Union(3, 7):
 
         [0] ← root of combined set
        / | \  \
      [1][2][3][5]
          |    / \
         [4] [6] [7]
 
parent: [0, 0, 0, 0, 2, 0, 5, 5]
        ↑  ↑  ↑  ↑  ↑  ↑  ↑  ↑
idx:    0  1  2  3  4  5  6  7
                      ↑
                  Changed from 5 to 0!
 
Combined set = {0, 1, 2, 3, 4, 5, 6, 7}
 
Verification:
- Find(3) = 0 ✓
- Find(7) → 5 → 0 ✓
- connected(3, 7) = (0 === 0) = true ✓

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

// Union(x, x) - element with itself
function demonstrateSelfUnion() {
    const uf = new UnionFind(5);
    
    console.log("Before Union(2, 2):");
    console.log("setCount:", uf.getSetCount());  // 5
    
    const merged = uf.union(2, 2);
    
    console.log("After Union(2, 2):");
    console.log("merged:", merged);              // false
    console.log("setCount:", uf.getSetCount());  // 5 (unchanged)
}
 
// Explanation:
// Find(2) = 2 (it's its own root initially)
// Find(2) = 2 (same thing)
// rootX === rootY, so no merge occurs
// This is correct! Element is already "connected" to itself

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

// Union(x, y) when x and y are already connected
function demonstrateRedundantUnion() {
    const uf = new UnionFind(5);
    
    uf.union(0, 1);  // {0, 1}
    uf.union(1, 2);  // {0, 1, 2}
    
    console.log("Before redundant Union(0, 2):");
    console.log("connected(0, 2):", uf.connected(0, 2));  // true
    console.log("setCount:", uf.getSetCount());           // 3
    
    const merged = uf.union(0, 2);  // Already connected!
    
    console.log("After redundant Union(0, 2):");
    console.log("merged:", merged);                       // false
    console.log("setCount:", uf.getSetCount());           // 3 (unchanged)
}
 
// Explanation:
// Find(0) = root of {0, 1, 2}
// Find(2) = same root
// rootX === rootY, so no merge occurs
// This idempotency is essential for correctness

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

Sequence: Union(0,1), Union(1,2), Union(2,3), Union(3,4)
 
After Union(0,1):     parent[1] = 0
  [0]
   |
  [1]
 
After Union(1,2):     Find(1)=0, Find(2)=2, parent[2] = 0
  [0]
  / \
 [1][2]
 
After Union(2,3):     Find(2)=0, Find(3)=3, parent[3] = 0
    [0]
   / | \
  [1][2][3]
 
After Union(3,4):     Find(3)=0, Find(4)=4, parent[4] = 0
      [0]
    / | | \
   [1][2][3][4]
 
This creates a shallow tree! Find is O(1) for all elements.
 
─────────────────────────────────────────────────────────
 
BUT consider this sequence instead:
Union(1,0), Union(2,1), Union(3,2), Union(4,3)
(Note: we're passing arguments in reverse order)
 
After Union(1,0):     Find(1)=1, Find(0)=0, parent[0] = 1
  [1]
   |
  [0]
 
After Union(2,1):     Find(2)=2, Find(1)=1, parent[1] = 2
    [2]
     |
    [1]
     |
    [0]
 
After Union(3,2):     Find(3)=3, Find(2)=2, parent[2] = 3
      [3]
       |
      [2]
       |
      [1]
       |
      [0]
 
After Union(4,3):     Find(4)=4, Find(3)=3, parent[3] = 4
        [4]
         |
        [3]
         |
        [2]
         |
        [1]
         |
        [0]
 
This creates a CHAIN! Find(0) = O(n) = 4 hops!

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

/**
 * Naive Union-Find (Disjoint Set Union) Implementation
 * 
 * This implementation is functionally correct but lacks the
 * optimizations (path compression, union by rank) needed for
 * optimal performance at scale.
 * 
 * Time Complexity:
 *   - Constructor: O(n)
 *   - find: O(n) worst case (chain), O(1) best case (root is direct parent)
 *   - union: O(n) worst case (dominated by two find calls)
 *   - connected: O(n) worst case (dominated by two find calls)
 * 
 * Space Complexity: O(n)
 */
class NaiveUnionFind {
    private parent: number[];
    private count: number;     // Number of disjoint sets
    private size: number[];    // Size of each tree (rooted at that index)
    
    /**
     * Initialize Union-Find with n elements (0 to n-1).
     * Each element starts in its own singleton set.
     */
    constructor(n: number) {
        // Every element is its own parent initially (each is a root)
        this.parent = Array.from({ length: n }, (_, i) => i);
        
        // n elements means n disjoint sets initially
        this.count = n;
        
        // Each tree starts with size 1
        this.size = new Array(n).fill(1);
    }
    
    /**
     * Find the root (representative) of the set containing x.
     * 
     * Elements in the same set share the same root.
     * Root is identified by parent[x] === x.
     */
    find(x: number): number {
        // Validation
        if (x < 0 || x >= this.parent.length) {
            throw new Error(`Element ${x} out of bounds`);
        }
        
        // Traverse parent chain until we reach the root
        while (this.parent[x] !== x) {
            x = this.parent[x];
        }
        return x;
    }
    
    /**
     * Merge the sets containing x and y.
     * 
     * @returns true if a merge occurred, false if already connected
     */
    union(x: number, y: number): boolean {
        const rootX = this.find(x);
        const rootY = this.find(y);
        
        // Already in the same set
        if (rootX === rootY) {
            return false;
        }
        
        // Merge: attach rootY's tree under rootX
        // (Arbitrary choice - we'll optimize this in union by rank)
        this.parent[rootY] = rootX;
        
        // Update size of the merged tree
        this.size[rootX] += this.size[rootY];
        
        // One fewer disjoint set
        this.count--;
        
        return true;
    }
    
    /**
     * Check if x and y are in the same set.
     */
    connected(x: number, y: number): boolean {
        return this.find(x) === this.find(y);
    }
    
    /**
     * Get the number of disjoint sets.
     * Decreases by 1 with each successful union.
     */
    getCount(): number {
        return this.count;
    }
    
    /**
     * Get the size of the set containing x.
     * Returns the total number of elements in x's set.
     */
    getSize(x: number): number {
        const root = this.find(x);
        return this.size[root];
    }
    
    /**
     * Debug: Print the internal state.
     */
    debug(): void {
        console.log("parent:", this.parent);
        console.log("size:  ", this.size);
        console.log("count: ", this.count);
    }
}

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

function demonstrateNaiveUnionFind() {
    const uf = new NaiveUnionFind(10);  // Elements 0-9
    
    console.log("Initial state:");
    console.log("Count:", uf.getCount());  // 10 (each element is its own set)
    
    // Build some connections
    uf.union(0, 1);
    uf.union(2, 3);
    uf.union(4, 5);
    uf.union(6, 7);
    uf.union(8, 9);
    
    console.log("\nAfter 5 unions:");
    console.log("Count:", uf.getCount());  // 5 (five pairs)
    
    // Query connectivity
    console.log("connected(0, 1):", uf.connected(0, 1));  // true
    console.log("connected(0, 2):", uf.connected(0, 2));  // false
    
    // Merge two pairs
    uf.union(1, 3);  // Merges {0,1} with {2,3}
    
    console.log("\nAfter merging pairs:");
    console.log("connected(0, 2):", uf.connected(0, 2));  // true
    console.log("getSize(0):", uf.getSize(0));            // 4
    console.log("Count:", uf.getCount());                 // 4
    
    // Create one giant component
    uf.union(0, 4);
    uf.union(4, 6);
    uf.union(6, 8);
    
    console.log("\nAfter connecting all:");
    console.log("Count:", uf.getCount());  // 1 (all connected)
    console.log("getSize(5):", uf.getSize(5));  // 10 (all elements)
}
 
// Output:
// Initial state:
// Count: 10
//
// After 5 unions:
// Count: 5
// connected(0, 1): true
// connected(0, 2): false
//
// After merging pairs:
// connected(0, 2): true
// getSize(0): 4
// Count: 4
//
// After connecting all:
// Count: 1
// getSize(5): 10

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

Consider n elements and this sequence of operations:
 
1. Union(1, 0)  → Creates chain: 0 → 1
2. Union(2, 1)  → Find(2)=O(1), Find(1)=O(1)  → 0 → 1 → 2
3. Union(3, 2)  → Find(3)=O(1), Find(2)=O(2)  → 0 → 1 → 2 → 3
4. Union(4, 3)  → Find(4)=O(1), Find(3)=O(3)  → 0 → 1 → 2 → 3 → 4
...
n. Union(n-1, n-2) → Find(n-1)=O(1), Find(n-2)=O(n-2)
 
Total time for n-1 unions:
= O(1 + 1) + O(1 + 2) + O(1 + 3) + ... + O(1 + (n-2))
= O(n) + O(1 + 2 + 3 + ... + (n-2))
= O(n) + O(n²/2)
= O(n²)
 
Then, m Find operations on element 0:
Each Find(0) traverses the entire chain: O(n) each
m × O(n) = O(mn)
 
Total for n unions + m finds: O(n² + mn) = O(n² + mn)
 
Compare to optimal Union-Find (with optimizations):
Same sequence: O(n + m·α(n)) ≈ O(n + m) where α(n) ≤ 4
 
For n = 1,000,000 and m = 1,000,000:
Naive:    O(10¹² + 10¹²) = O(2 × 10¹²) operations
Optimal:  O(10⁶ + 10⁶) ≈ O(2 × 10⁶) operations
 
That's about ONE MILLION times slower!

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

Initial State: 8 elements, each in its own set
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
[0] [1] [2] [3] [4] [5] [6] [7]
 
parent: [0, 1, 2, 3, 4, 5, 6, 7]
Sets: {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}}
Count: 8
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Operation 1: Union(0, 1)
Find(0) = 0, Find(1) = 1
Different roots → parent[1] = 0
 
     [0]
      |
     [1]
 
[0]     [2] [3] [4] [5] [6] [7]
 |
[1]
 
parent: [0, 0, 2, 3, 4, 5, 6, 7]
Sets: {{0,1}, {2}, {3}, {4}, {5}, {6}, {7}}
Count: 7
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Operation 2: Union(2, 3)
Find(2) = 2, Find(3) = 3
Different roots → parent[3] = 2
 
[0]     [2]     [4] [5] [6] [7]
 |       |
[1]     [3]
 
parent: [0, 0, 2, 2, 4, 5, 6, 7]
Sets: {{0,1}, {2,3}, {4}, {5}, {6}, {7}}
Count: 6
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Operation 3: Union(4, 5)
 
[0]     [2]     [4]     [6] [7]
 |       |       |
[1]     [3]     [5]
 
parent: [0, 0, 2, 2, 4, 4, 6, 7]
Count: 5
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Operation 4: Union(6, 7)
 
[0]     [2]     [4]     [6]
 |       |       |       |
[1]     [3]     [5]     [7]
 
parent: [0, 0, 2, 2, 4, 4, 6, 6]
Count: 4
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Operation 5: Union(1, 3)
Find(1) = 1 → 0
Find(3) = 3 → 2
Different roots → parent[2] = 0
 
    [0]
   / | 
  [1][2]
      |
     [3]
 
     [0]         [4]     [6]
    / |           |       |
  [1][2]         [5]     [7]
      |
     [3]
 
parent: [0, 0, 0, 2, 4, 4, 6, 6]
Sets: {{0,1,2,3}, {4,5}, {6,7}}
Count: 3
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Operation 6: Union(5, 7)
Find(5) = 5 → 4
Find(7) = 7 → 6
Different roots → parent[6] = 4
 
     [0]              [4]
    / |              / | 
  [1][2]           [5][6]
      |                |
     [3]              [7]
 
parent: [0, 0, 0, 2, 4, 4, 4, 6]
Sets: {{0,1,2,3}, {4,5,6,7}}
Count: 2
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Operation 7: Union(0, 4)
Find(0) = 0
Find(4) = 4
Different roots → parent[4] = 0
 
          [0]
       /  |  \  \
     [1] [2] [4]
          |  / \
         [3][5][6]
               |
              [7]
 
parent: [0, 0, 0, 2, 0, 4, 4, 6]
Sets: {{0,1,2,3,4,5,6,7}}
Count: 1
 
All elements now connected!
 
Query: connected(3, 7)?
Find(3): 3 → 2 → 0  (2 hops)
Find(7): 7 → 6 → 4 → 0  (3 hops)
Both return 0 → YES, connected!