DSU, MST, and offline activation · HTML
Over objects V, process union(a,b), find(x), and connected(a,b); the relation is an equivalence relation and edges are insertion-only.
Recognition signals
- Repeated merge-group and same-group operations
- Connectivity matters but the actual path does not
- The relation is transitive
- Edges arrive without deletion
- Component counts or sizes are required
False friends
| Signal | Why it is different |
|---|
| A path or distance is required | DSU discards internal paths; use BFS, Dijkstra, or an explicit graph. |
| Arbitrary online edge deletion | Plain DSU cannot split a set; consider reverse-time processing, rollback DSU, or a dynamic-connectivity structure. |
Core invariant
Each set is a parent-pointer tree with one representative root; size is meaningful only at roots.
State, transition, and processing order
| Item | Definition |
|---|
| State | Parent pointers, root sizes, and an optional component counter. |
| Transition | find compresses the path; union finds both roots and attaches the smaller tree under the larger. |
| Frontier / order | There is no search frontier: processed relations are summarized by roots, while unprocessed operations remain in the stream. |
Python skeleton
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.sz = [1] * n
self.components = n
def find(self, x):
while x != self.p[x]:
self.p[x] = self.p[self.p[x]]
x = self.p[x]
return x
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b: return False
if self.sz[a] < self.sz[b]: a, b = b, a
self.p[b] = a
self.sz[a] += self.sz[b]
self.components -= 1
return True
def connected(self, a, b):
return self.find(a) == self.find(b)
Correctness sketch
- Initially every object is a singleton, so the invariant holds.
- union links only distinct roots, exactly merging two equivalence classes.
- Path compression only redirects nodes to ancestors in the same tree, preserving membership.
- Induction over operations gives equal representatives exactly for connected objects.
Complexity
| Time | Space | Parameters |
|---|
| O((n+m) α(n)) total for m operations | O(n) | n objects, m operations, inverse-Ackermann function α |
Edge cases
- A duplicate union must not change counters
- An object is always connected to itself
- Read size through a representative
- Compress sparse labels first
- Define behavior for n=0
Error patterns
| Pattern | Why it fails / fix |
|---|
| Comparing parent entries directly | Parents may not be roots; compare find results. |
| Linking ordinary nodes | Only roots should be linked, or sizes and tree depth become invalid. |
| Counting a duplicate merge | Return immediately when both roots already match. |
Selection and exclusion rules
- Insertion-only connectivity: choose DSU first.
- Need a concrete path or distance: use graph search.
- Deletions become insertions in reverse time: use offline DSU.
- Sparse labels: map them to a compact integer range.
Original micro-example
| Part | Detail |
|---|
| Result | {0,1,3,4} becomes one component, 2 stays alone, and components=2. |
| Scenario | Five devices connect 0-1, 3-4, then 1-4. |
| Walkthrough | The first two links form separate trees; the third links their roots, making connected(0,3) true. |
Recall prompts
My notes