DSA Notes

Graphs

Disjoint Set Union

Track which items belong together as groups merge.

The idea

A disjoint set union keeps elements in groups and supports two operations: find(x), the representative of x’s group, and unite(a, b), which merges two groups.

Each element points to a parent; the root of the tree is the representative. Path compression (point straight at the root after a find) and union by size (hang the smaller tree under the larger) make both operations practically O(1).

It answers “are a and b connected?” while edges are being added, drives Kruskal’s minimum spanning tree, and handles deletions when the queries are processed in reverse.

Sample problem

684. Redundant Connection ↗ Medium

A tree with n nodes had one extra edge added. Given the n edges in order, return the edge that can be removed so the rest is a tree. If several qualify, return the one that appears last.

edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
output = [1,4]

Why the solution works

Add the edges one at a time. An edge is useful if it joins two parts that were separate, and redundant if its two ends were already connected: then it closes a cycle.

“Are these two nodes already connected?” while connections keep being added is exactly what a disjoint set union answers: compare the two representatives with find, and merge the groups with one assignment.

The first edge whose ends share a representative is the one that completes the cycle, and so it is the last edge of that cycle in the input.

Complexity: O(n · α(n)) time, practically linear. O(n) memory.

Watch out

  • Compare find(a) with find(b), never parent[a] with parent[b].
  • A DSU cannot split groups. If edges are removed, read all queries first and add the edges backwards.
  • Call init before the first operation.
Watch it run

Practise on LeetCode