Union-Find (Disjoint Set)

Foundations

So far, every question needed a walk over the graph's edges. Now, what if edges arrive one at a time, and after each one you must say whether two nodes are connected, without walking again?

Union-find keeps each component as a tree of parent pointers: parent[x] is x's parent, and the root, its own parent, names the component. find(x) follows parents to the root; union(a, b) finds both roots and, if they differ, points one at the other. Path compression shortcuts every node a find passes toward the root, here by halving each path, which keeps trees shallow: near-O(1) per operation.

Start with parent = [0, 1, 2, 3, 4], five components. union(0, 1) points 0 at 1, union(2, 3) points 2 at 3, and union(1, 3) points root 1 at root 3. Now find(0) walks 0 → 1 → 3, and compression points 0 straight at 3. Two roots remain, 3 and 4: two components.

• Graphs

  Number of Islands counted components with a flood. Union-find counts them without walking the graph.

  Open lesson

Case Scenario

Number of Connected Components gives n nodes and a list of undirected edges and asks how many components they form. Start with n roots and union the endpoints of each edge; every union that joins two different roots removes one component. For n = 5 and edges = [[0, 1], [1, 2], [3, 4]], three unions succeed, so the answer is 2.

The direct approach builds an adjacency list and counts how many depth-first walks it takes to visit every node. That is linear for one question, but it keeps every edge in memory, O(V + E), and if edges keep arriving, each new question means walking the whole graph again.