Union-Find & Minimum Spanning Trees

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Union-Find: parent[] forest, root = group name. find walks up; union links two roots. MST: the cheapest set of n − 1 edges connecting everything.

   #1
2. ↯use it when

   Pairs or edges arrive and you ask "same group?", count groups, spot the edge that closes a cycle — or "connect all at minimum cost".

   #2
3. { }template

   find: if (parent[x] != x) parent[x] = find(parent[x]); · union: roots equal → false; else smaller size under bigger, count--.

   #3
4. O( )cost

   Both tricks: O(α(n)) amortized per op — effectively constant. Kruskal O(E log E). Lazy Prim O(E log E). Dense Prim O(V²).

   #4
5. !trap

   parent[a] == parent[b] is not "same set" — compare find(a) == find(b). And link roots: parent[find(a)] = find(b).

   #5
6. !trap

   DSU ignores direction: never use it for directed cycles (use DFS colours or Kahn's). It also can't split a group.

   #6
7. ✦pro tip

   Valid tree = exactly n − 1 edges + no union fails. Make network connected = components − 1, if cables ≥ n − 1.

   #7
8. ✦pro tip

   Every pair of points is an edge? Use dense Prim with a best[] array — no 5-lakh-edge list to build and sort.

   #8
9. !trap

   Kruskal that ends with fewer than n − 1 edges means disconnected — there is no spanning tree. Check it.

   #9

Shaky on a card? Open the chapter or flip its recall cards.