facinick

Quick Find

When I first encountered the concept of dynamic connectivity, it felt like stumbling upon a hidden superpower in the world of computer science. 🕵️‍♀️ The Union-Find algorithm isn't just a data structure—it's a mathematical marvel that can solve problems ranging from social network analysis to physical system modeling.

👩‍💻 Dive Straight Into the Code

If you’re only interested in the raw code, here’s where you can explore the implementations directly:

Feel free to browse and adapt the code for your own projects. 🚀

🧠 Understanding Dynamic Connectivity

Let's start with a fundamental question: How do we efficiently track connections between objects?

Imagine you have a set of objects, and you want to:

  • Connect specific objects
  • Check if two objects are already connected
  • Determine the number of distinct groups or components

This is the essence of the dynamic connectivity problem.

The Core Challenges

When designing a Union-Find data structure, we face several critical constraints:

  • Handle a potentially massive number of objects (N can be huge)
  • Support multiple operations efficiently
  • Manage both union commands and connectivity queries

The Union-Find API

Here's what our ideal data structure needs to support:

1class UnionFind {
2    constructor(N: number) {
3        // Initialize with N objects (0 to N-1)
4    }
5
6    union(p: number, q: number): void {
7        // Add connection between p and q
8    }
9
10    connected(p: number, q: number): boolean {
11        // Are p and q in the same component?
12        return false;
13    }
14
15    find(p: number): number {
16        // Find the component identifier for p
17        return -1;
18    }
19
20    count(): number {
21        // Number of distinct components
22        return 0;
23    }
24}
1class UnionFind {
2    constructor(N: number) {
3        // Initialize with N objects (0 to N-1)
4    }
5
6    union(p: number, q: number): void {
7        // Add connection between p and q
8    }
9
10    connected(p: number, q: number): boolean {
11        // Are p and q in the same component?
12        return false;
13    }
14
15    find(p: number): number {
16        // Find the component identifier for p
17        return -1;
18    }
19
20    count(): number {
21        // Number of distinct components
22        return 0;
23    }
24}

🌟 The Journey of Optimizations

Quick Find: The Naive First Attempt

Our first approach might look straightforward:

1class QuickFind {
2
3  // interperation of the id array
4  // p and q are connected if they have the same id
5  private id: Array<number>;
6  private N: number;
7  private nComponents: number;
8
9  constructor(n: number) {
10    this.N = n;
11    this.nComponents = n;
12    this.id = new Array<number>(n).fill(0);
13
14    // each id or node is connected to only itself. so let them have same value as their id
15    this.id.forEach((_, index, array) => {
16      array[index] = index;
17    })
18  }
19
20  // every element that's in same component as p, will have same value in id array.
21  // find all such and change them to id of q node
22  // N operations everytime a union is performed.
23  public union(p: number, q: number): void {
24
25    if(this.connected(p,q)) {
26      return;
27    }
28
29    const idOfComponentContainingP = this.id[p];
30    const idOfComponentContainingQ = this.id[q];
31
32    this.id.forEach((_,index,array) => {
33      // if it belongs to component same as p
34      if(array[index] === idOfComponentContainingP) {
35        // change it to make it a part of component same as q
36        array[index] = idOfComponentContainingQ
37      }
38    })
39
40    this.nComponents -= 1;
41  }
42
43  // constant time operation every time connected is performed
44  public connected(p: number, q: number): boolean {
45    return this.id[p] === this.id[q];
46  }
47
48  // same as root(p: number): number
49  // every component has one id, lets call it it's root. 
50  public find(p: number): number {
51    return this.id[p]
52  }
53
54  public count(): number {
55    return this.nComponents;
56  }
57
58  public display(): void {
59    const n = this.id.length;
60    let result = "";
61    for (let i = 0; i < n; i++) {
62        result += `${this.id[i]} `;
63    }
64    console.log(`[${result}]`);
65  }
66}
67
68export {
69  QuickFind
70};
1class QuickFind {
2
3  // interperation of the id array
4  // p and q are connected if they have the same id
5  private id: Array<number>;
6  private N: number;
7  private nComponents: number;
8
9  constructor(n: number) {
10    this.N = n;
11    this.nComponents = n;
12    this.id = new Array<number>(n).fill(0);
13
14    // each id or node is connected to only itself. so let them have same value as their id
15    this.id.forEach((_, index, array) => {
16      array[index] = index;
17    })
18  }
19
20  // every element that's in same component as p, will have same value in id array.
21  // find all such and change them to id of q node
22  // N operations everytime a union is performed.
23  public union(p: number, q: number): void {
24
25    if(this.connected(p,q)) {
26      return;
27    }
28
29    const idOfComponentContainingP = this.id[p];
30    const idOfComponentContainingQ = this.id[q];
31
32    this.id.forEach((_,index,array) => {
33      // if it belongs to component same as p
34      if(array[index] === idOfComponentContainingP) {
35        // change it to make it a part of component same as q
36        array[index] = idOfComponentContainingQ
37      }
38    })
39
40    this.nComponents -= 1;
41  }
42
43  // constant time operation every time connected is performed
44  public connected(p: number, q: number): boolean {
45    return this.id[p] === this.id[q];
46  }
47
48  // same as root(p: number): number
49  // every component has one id, lets call it it's root. 
50  public find(p: number): number {
51    return this.id[p]
52  }
53
54  public count(): number {
55    return this.nComponents;
56  }
57
58  public display(): void {
59    const n = this.id.length;
60    let result = "";
61    for (let i = 0; i < n; i++) {
62        result += `${this.id[i]} `;
63    }
64    console.log(`[${result}]`);
65  }
66}
67
68export {
69  QuickFind
70};

The Problem: This approach is catastrophically slow!

  • Initialization: O(N)
  • Union operation: O(N²)
  • Connected check: O(1)

For 10⁹ operations on 10⁹ objects, this would take over 30 years of computation time. 😱

Quick Union: A Lazy Approach

We can do better by using a tree-like structure:

1class QuickUnion {
2
3  // this array now represents a set of trees. each entry points to id of it's aprent in the array
4  // initially all are their own parent
5  private id: Array<number>;
6  private N: number;
7  private nComponents: number;
8
9  constructor(n: number) {
10    this.N = n;
11    this.nComponents = n;
12
13    this.id = new Array<number>(n).fill(0);
14    this.id.forEach((_, index, array) => {
15      // every element / node is their own parent hence storing value of their own id;
16      array[index] = index;
17    })
18  }
19
20  union(p: number, q: number): void {
21
22    if(this.connected(p,q)) {
23      return;
24    }
25
26    const rootP = this.find(p);
27    const rootQ = this.find(q);
28
29    this.id[rootP] = rootQ;
30    this.nComponents -= 1;
31  }
32
33  // this time same as checking if p and q have same root / same identifier for their component.
34  // earlier we were storing the identifier tiself in array, but now we are storing parent
35  // so new indirect identifier is the ROOT. keep going from parent to parent untill u cant
36  connected(p: number, q: number): boolean {
37    return this.find(p) === this.find(q);
38  }
39
40  // same as root(p: number): number
41  find(p: number): number {
42    let child = p;
43    let parent = this.id[p];
44
45    // in case we find root element, it's value will point to it's own id. 
46    // child is the element / id / node
47    // parent is the value of that id in array, id of another element. sighs
48    while(child !== parent) {
49      child = parent
50      parent = this.id[child]
51    }
52    return parent;
53  }
54
55  count(): number {
56    return this.nComponents;
57  }
58
59  public display(): void {
60    const n = this.id.length;
61    let result = "";
62    for (let i = 0; i < n; i++) {
63        result += `${this.id[i]} `;
64    }
65    console.log(`[${result}]`);
66  }
67}
68
69export { QuickUnion };
1class QuickUnion {
2
3  // this array now represents a set of trees. each entry points to id of it's aprent in the array
4  // initially all are their own parent
5  private id: Array<number>;
6  private N: number;
7  private nComponents: number;
8
9  constructor(n: number) {
10    this.N = n;
11    this.nComponents = n;
12
13    this.id = new Array<number>(n).fill(0);
14    this.id.forEach((_, index, array) => {
15      // every element / node is their own parent hence storing value of their own id;
16      array[index] = index;
17    })
18  }
19
20  union(p: number, q: number): void {
21
22    if(this.connected(p,q)) {
23      return;
24    }
25
26    const rootP = this.find(p);
27    const rootQ = this.find(q);
28
29    this.id[rootP] = rootQ;
30    this.nComponents -= 1;
31  }
32
33  // this time same as checking if p and q have same root / same identifier for their component.
34  // earlier we were storing the identifier tiself in array, but now we are storing parent
35  // so new indirect identifier is the ROOT. keep going from parent to parent untill u cant
36  connected(p: number, q: number): boolean {
37    return this.find(p) === this.find(q);
38  }
39
40  // same as root(p: number): number
41  find(p: number): number {
42    let child = p;
43    let parent = this.id[p];
44
45    // in case we find root element, it's value will point to it's own id. 
46    // child is the element / id / node
47    // parent is the value of that id in array, id of another element. sighs
48    while(child !== parent) {
49      child = parent
50      parent = this.id[child]
51    }
52    return parent;
53  }
54
55  count(): number {
56    return this.nComponents;
57  }
58
59  public display(): void {
60    const n = this.id.length;
61    let result = "";
62    for (let i = 0; i < n; i++) {
63        result += `${this.id[i]} `;
64    }
65    console.log(`[${result}]`);
66  }
67}
68
69export { QuickUnion };

The Improvement:

  • Trees are flatter
  • Union is cheaper
  • But find can still be expensive

Weighted Quick Union: Balancing the Tree

The breakthrough comes with weighted quick union:

1/*
2  Proposition: Depth of any node is at max Log(n), therefore
3  cost of finding roots is easier, in previous (quick union, this wasn't the case)
4*/
5
6// depth of any node here is at most log base 2 of N
7
8class WeightedQuickUnion {
9
10  private id: Array<number>;
11  private N: number;
12  private nComponents: number;
13  // keeps weight of tree with root at the item
14  // = number of items with root as the node INDEX
15  private weights: Array<number>;
16  // for visualisation, not required for this algorithm
17  // private tree: Map<number, Array<number>>;
18
19  /*
20    cost: n
21  */
22  constructor(n: number) {
23    this.N = n;
24    this.nComponents = n;
25
26    // not needed for this algorithm
27    // this.tree = new Map();
28
29    this.id = new Array<number>(n).fill(0);
30    this.id.forEach((_, index, array) => {
31      // every element / node is their own parent hence storing value of their own id;
32      array[index] = index;
33    })
34
35    // weight at node i is the number of elements that has it as it's root.
36    this.weights = new Array<number>(n).fill(1);
37  }
38
39  // same as root(p: number): number
40  find(p: number): number {
41    let child = p;
42    let parent = this.id[p];
43
44    // in case we find root element, it's value will point to it's own id. 
45    // child is the element / id / node
46    // parent is the value of that id in array, id of another element. sighs
47    while(child !== parent) {
48      child = parent
49      parent = this.id[child]
50    }
51    return parent;
52  }
53
54  // constant time operation every time connected is performed
55  public connected(p: number, q: number): boolean {
56    return this.find(p) === this.find(q);
57  }
58
59  /*
60    link root of smaller tree to root of larger tree
61  */
62  public union(p: number, q: number): void {
63
64    const rootP = this.find(p)
65    const rootQ = this.find(q)
66
67    if(rootP === rootQ) {
68      return;
69    }
70
71    // p is in smaller tree, make p's root's parent q's root
72    if(this.weights[rootP] < this.weights[rootQ]) {
73      this.id[rootP] = rootQ
74      this.weights[rootQ] = this.weights[rootQ] + this.weights[rootP];
75
76      // Update tree structure
77      // this.tree.has(rootQ) ? this.tree.get(rootQ)?.push(rootP) : this.tree.set(rootQ, [rootP])
78    } else {
79      this.id[rootQ] = rootP
80      this.weights[rootP] = this.weights[rootQ] + this.weights[rootP]
81
82      // Update tree structure
83      // this.tree.has(rootP) ? this.tree.get(rootP)?.push(rootQ) : this.tree.set(rootP, [rootQ])
84    }
85
86    this.nComponents -= 1;
87  }
88
89  count(): number {
90    return this.nComponents;
91  }
92
93  public display(): void {
94    const n = this.id.length;
95    let result = "";
96    for (let i = 0; i < n; i++) {
97        result += `${this.id[i]} `;
98    }
99    console.log(`[${result}]`);
100  }
101
102  public getData(): typeof this.id {
103    return this.id
104  }
105
106  public findComponent(p: number): Array<number> {
107    const rootP = this.find(p);
108    const component = [];
109
110    for (let i = 0; i < this.N; i++) {
111      if (this.find(i) === rootP) {
112        component.push(i);
113      }
114    }
115
116    return component;
117  }
118
119  // public getTree(): Map<number, Array<number>> {
120  //   return this.tree;
121  // }
122}
123
124export { WeightedQuickUnion };
125
1/*
2  Proposition: Depth of any node is at max Log(n), therefore
3  cost of finding roots is easier, in previous (quick union, this wasn't the case)
4*/
5
6// depth of any node here is at most log base 2 of N
7
8class WeightedQuickUnion {
9
10  private id: Array<number>;
11  private N: number;
12  private nComponents: number;
13  // keeps weight of tree with root at the item
14  // = number of items with root as the node INDEX
15  private weights: Array<number>;
16  // for visualisation, not required for this algorithm
17  // private tree: Map<number, Array<number>>;
18
19  /*
20    cost: n
21  */
22  constructor(n: number) {
23    this.N = n;
24    this.nComponents = n;
25
26    // not needed for this algorithm
27    // this.tree = new Map();
28
29    this.id = new Array<number>(n).fill(0);
30    this.id.forEach((_, index, array) => {
31      // every element / node is their own parent hence storing value of their own id;
32      array[index] = index;
33    })
34
35    // weight at node i is the number of elements that has it as it's root.
36    this.weights = new Array<number>(n).fill(1);
37  }
38
39  // same as root(p: number): number
40  find(p: number): number {
41    let child = p;
42    let parent = this.id[p];
43
44    // in case we find root element, it's value will point to it's own id. 
45    // child is the element / id / node
46    // parent is the value of that id in array, id of another element. sighs
47    while(child !== parent) {
48      child = parent
49      parent = this.id[child]
50    }
51    return parent;
52  }
53
54  // constant time operation every time connected is performed
55  public connected(p: number, q: number): boolean {
56    return this.find(p) === this.find(q);
57  }
58
59  /*
60    link root of smaller tree to root of larger tree
61  */
62  public union(p: number, q: number): void {
63
64    const rootP = this.find(p)
65    const rootQ = this.find(q)
66
67    if(rootP === rootQ) {
68      return;
69    }
70
71    // p is in smaller tree, make p's root's parent q's root
72    if(this.weights[rootP] < this.weights[rootQ]) {
73      this.id[rootP] = rootQ
74      this.weights[rootQ] = this.weights[rootQ] + this.weights[rootP];
75
76      // Update tree structure
77      // this.tree.has(rootQ) ? this.tree.get(rootQ)?.push(rootP) : this.tree.set(rootQ, [rootP])
78    } else {
79      this.id[rootQ] = rootP
80      this.weights[rootP] = this.weights[rootQ] + this.weights[rootP]
81
82      // Update tree structure
83      // this.tree.has(rootP) ? this.tree.get(rootP)?.push(rootQ) : this.tree.set(rootP, [rootQ])
84    }
85
86    this.nComponents -= 1;
87  }
88
89  count(): number {
90    return this.nComponents;
91  }
92
93  public display(): void {
94    const n = this.id.length;
95    let result = "";
96    for (let i = 0; i < n; i++) {
97        result += `${this.id[i]} `;
98    }
99    console.log(`[${result}]`);
100  }
101
102  public getData(): typeof this.id {
103    return this.id
104  }
105
106  public findComponent(p: number): Array<number> {
107    const rootP = this.find(p);
108    const component = [];
109
110    for (let i = 0; i < this.N; i++) {
111      if (this.find(i) === rootP) {
112        component.push(i);
113      }
114    }
115
116    return component;
117  }
118
119  // public getTree(): Map<number, Array<number>> {
120  //   return this.tree;
121  // }
122}
123
124export { WeightedQuickUnion };
125

Key Insight: By always attaching the smaller tree to the larger one, we keep the tree nearly balanced.

Path Compression: The Final Optimization

The ultimate optimization is path compression:

1// same as root(p: number): number
2  find(p: number): number | null {
3
4    if(p < 0 || p >= this.N) {
5      return null
6    }
7
8    let child = p;
9    let parent = this.id[p];
10
11    // in case we find root element, it's value will point to it's own id. 
12    // child is the element / id / node
13    // parent is the value of that id in array, id of another element. sighs
14    while(child !== parent) {
15      child = parent
16      parent = this.id[child]
17    }
18
19    // apply path compression here ----------------------------
20    child = p;
21    while (child !== parent) {
22      let next = this.id[child];
23      this.id[child] = parent;
24      child = next;
25    }
26    // --------------------------------------------------------
27    return parent;
28  }
1// same as root(p: number): number
2  find(p: number): number | null {
3
4    if(p < 0 || p >= this.N) {
5      return null
6    }
7
8    let child = p;
9    let parent = this.id[p];
10
11    // in case we find root element, it's value will point to it's own id. 
12    // child is the element / id / node
13    // parent is the value of that id in array, id of another element. sighs
14    while(child !== parent) {
15      child = parent
16      parent = this.id[child]
17    }
18
19    // apply path compression here ----------------------------
20    child = p;
21    while (child !== parent) {
22      let next = this.id[child];
23      this.id[child] = parent;
24      child = next;
25    }
26    // --------------------------------------------------------
27    return parent;
28  }

Real-World Applications

Union-Find isn't just a theoretical construct. It's used in:

  • Percolation models
  • Social network analysis
  • Image processing
  • Game development (Go, Hex)
  • Kruskal's minimum spanning tree algorithm

The Percolation Problem

One of the most fascinating applications is the percolation model:

  • Imagine an N×N grid
  • Each site can be open or blocked
  • Goal: Determine if a path exists from top to bottom

Percolating Grid

Try tapping/clicking the top layer, breaking them will allow water to come through!

System doesn't percolate

The magic happens at a critical threshold (around 0.592746), where the system transitions from not percolating to percolating.

Performance Breakdown

AlgorithmInitializeUnionConnectedNotes
Quick FindNN1Too slow for large N
Quick UnionNNNTall trees are problematic
Weighted Quick UnionNlog Nlog NMuch more efficient
Weighted Quick Union + Path CompressionNnearly constantnearly constantAlmost optimal!

The Bigger Picture

Union-Find teaches us a crucial lesson in algorithm design:

  1. Start with a naive solution
  2. Identify performance bottlenecks
  3. Incrementally optimize
  4. Use clever data structure transformations

Sometimes, a small tweak can transform an unusable algorithm into a blazing-fast solution!

Published By