Workspace

Problem workspace

3 day streakD

Disjoint Set Union (Union-Find)

MediumGraphsConnectivity

The challenge

Maintain components while undirected connections are added. Support find(u), union(u, v), and checking whether two vertices are connected.

Supports adding connections. Basic DSU does not support deletions or directed reachability.

Example

Union A–B, then B–C. Now find(A) equals find(C); union(A, C) returns false because they are already connected.

Use the walkthrough below to inspect the input and each state change.

See Union-Find, step by step

Follow the edges. Watch the state change.

Undirected · 6 vertices · 7 edgesA = 0, B = 1, …
Weighted graphUndirected graph with 6 vertices. Start with one component per vertex. Process the undirected edges as union operations. Representatives identify connectivity, not literal graph edges. The edge list and state table below provide the graph in text.4121831Aset 1Bset 2Cset 3Dset 4Eset 5Fset 6
CurrentVisited / acceptedUnvisitedLabels identify components or colors
Component representative
ABCDEF
ABCDEF
Step 01 / 9

Start with one component per vertex.

Process the undirected edges as union operations. Representatives identify connectivity, not literal graph edges.

parent[u] = u; size[u] = 1

Connectivity

6 component(s)
View input edges

A — B (4) · A — F (1) · F — B (2) · B — C (1) · F — E (8) · C — D (3) · D — E (1)

Put it into code

Represent each component as a parent tree and make repeated finds cheaper.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, u):
        while u != self.parent[u]:
            self.parent[u] = self.parent[self.parent[u]]
            u = self.parent[u]
        return u

    def union(self, u, v):
        a, b = self.find(u), self.find(v)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.components -= 1
        return True

# Example: vertices 0..5 (A..F in the diagram).
dsu = DSU(6)
dsu.union(0, 1)
dsu.union(1, 2)
connected = dsu.find(0) == dsu.find(2)  # True
merged = dsu.union(0, 2)  # False: already in one component.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap