Applications of DSU

Four canonical uses. Recognize the shape and the code is forty lines.

1. Connected components in an undirected graph

Given a graph as a list of edges, how many connected components are there? How big is each?

Plain DSU. For every edge (u, v), call union(u, v). At the end, the number of distinct roots = the number of components.

def count_components(n, edges):
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)
    return dsu.components       # we already maintain this as a counter

O((V + E) · α(V)). Linear-ish.

If you want a list of components rather than just a count:

from collections import defaultdict
groups = defaultdict(list)
for i in range(n):
    groups[dsu.find(i)].append(i)

DFS or BFS would also solve this in O(V + E). DSU wins when the graph is dynamic — edges arrive one at a time and you need to answer connectivity queries between them.

2. Cycle detection in an undirected graph

For each edge (u, v), before calling union, check find(u) == find(v):

• If they’re already in the same component, adding (u, v) would create a cycle.
• Otherwise, union(u, v) and continue.

def has_cycle(n, edges):
    dsu = DSU(n)
    for u, v in edges:
        if dsu.connected(u, v):
            return True
        dsu.union(u, v)
    return False

Note: this works for undirected graphs only. Directed-graph cycle detection needs DFS with a recursion-stack color (revisit Day 10 for the directed case).

This is also how you check whether n vertices and n - 1 edges form a tree: connectivity + no cycle.

3. Kruskal’s MST

Already met in Day 22, but worth re-anchoring here as the textbook DSU client.

def kruskal(n, edges):
    # edges = list of (weight, u, v)
    edges.sort()
    dsu = DSU(n)
    total = added = 0
    for w, u, v in edges:
        if dsu.union(u, v):
            total += w
            added += 1
            if added == n - 1:
                break
    return total if added == n - 1 else -1

The cycle-detection-via-union pattern is doing all the work. Without DSU, Kruskal’s would be O(E · V); with DSU it’s O(E log E) (dominated by the sort).

4. Weighted DSU — tracking offsets

A subtle but powerful extension: alongside parent[x], store weight[x] = some scalar that represents “the relationship between x and parent[x].”

Common interpretations:

• Distance: weight[x] = numeric distance to parent. After path compression, weight[x] = distance to root.
• Parity: weight[x] ∈ {0, 1} = same-team or other-team. Powers bipartite-checking under merges.
• Difference: for “equality with offset” constraints like x = y + 5.

The trick: when you compress the path during find, you must accumulate the weights so the recomputed weight[x] correctly represents the offset to the new parent (the root).

def find(self, x):
    if self.parent[x] != x:
        root = self.find(self.parent[x])
        self.weight[x] += self.weight[self.parent[x]]   # accumulate
        self.parent[x] = root
    return self.parent[x]

This pattern shows up in Satisfiability of Equality Equations, Evaluate Division (LeetCode 399 — actually solvable with weighted DSU instead of DFS), and various competitive-programming problems.

5. Implicit DSU on a grid

For grid problems where neighboring cells “merge” under some condition (flood fill, percolation), use a DSU indexed by r * cols + c. Each cell is an element; unioning happens when two neighbors satisfy the merge condition.

def cell_id(r, c, cols):
    return r * cols + c
 
dsu = DSU(rows * cols)
for r in range(rows):
    for c in range(cols):
        for dr, dc in ((0, 1), (1, 0)):       # only need right + down to avoid double-counting
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and should_merge(r, c, nr, nc):
                dsu.union(cell_id(r, c, cols), cell_id(nr, nc, cols))

Shows up in Number of Islands II (dynamic island merging as cells flip), Regions Cut by Slashes, percolation simulations.

6. Offline reverse processing

DSU has no efficient “split” (un-union). But many problems with edge deletions can be solved by processing the queries in reverse:

Given a graph with edges and a sequence of edge deletions, answer connectivity queries after each deletion.

Run the queries in reverse: start from the final graph (after all deletions), then process events in reverse, which turns deletions into insertions. DSU handles insertions perfectly.

The same trick works for problems like Bricks Falling When Hit (LeetCode 803), where bricks are removed and you need to know which other bricks fell — reverse it into “bricks added, what got connected to the roof?”

Decision table

Quick check

Next: basic warm-up questions to lock in the template, then practice problems.