Union–Find & Dijkstra
Merge groups in near-O(1) with union–find, and find cheapest weighted paths with a heap.
13 min, 0 of 4 activities solved
View cheatsheetGetting Python ready… examples can run in a moment.
Union–find (a.k.a. disjoint set union, DSU) tracks groups that only ever merge. Each group is a little tree; its root is the group's representative.
find(x): walk up parents to the root.union(a, b): find both roots; if they differ, hang one under the other.
Two tricks make both operations nearly O(1) (amortised α(n), which is ≤ 4 for any real n):
- path compression: after a
find, point every node on the path straight at the root - union by rank: hang the shorter tree under the taller one, so trees stay flat
Reach for it when edges arrive one at a time and you keep asking "are these two already connected?", e.g. detecting the edge that creates a cycle in an undirected graph.
A union–find class
union(0, 2) returns False: 0 and 2 were
already linked through 1 and 3, so that edge would
close a cycle. With union by rank a tree's height
stays O(log n), so the recursive find never gets
deep.
The unions above, one edge at a time
parent[x] = x: every node is the root of its own one-node group.
p under each node is its parent.
What does this print?
Weighted graphs need Dijkstra. When edges have different costs, BFS's "fewest edges" is no longer "cheapest": one 10-minute flight loses to three 1-minute hops.
Dijkstra's algorithm is BFS with a min-heap instead of a queue: always expand the node with the smallest known distance.
dist[src] = 0, heap =[(0, src)].- Pop
(d, node). Ifd > dist[node]it's a stale entry (a better one was already handled): skip it. - Relax each edge: if
d + w < dist[nxt], update it and push(d + w, nxt).
Cost: O(E log V) with heapq. It requires
non-negative weights.
Dijkstra with heapq, traced
The direct edge 0 → 1 costs 4, but 0 → 2 → 1
costs 3, so (4, 1) becomes stale and is skipped.
Once a node is popped with its true distance, it is
settled: nothing cheaper can come later, because
every other path starts from a node that is at least
as far away.
Dijkstra from 0
dist[0] = 0, everything else is infinity.
Labels show dist; the heap is listed smallest first.
What does this print?
Connectivity queries
Write connected(n, edges, queries): nodes are
0..n-1, edges are undirected pairs and each
query is a pair (a, b). Return a list of booleans,
one per query: are a and b in the same
component?
Use union–find: union every edge, then compare roots.
connected(5, [(0, 1), (1, 2), (3, 4)], [(0, 2), (0, 4)])
is [True, False].
Edges of an undirected graph arrive one by one. After each, you must report whether it created a cycle. Best tool?