Module 21 · Union-Find, Weighted Graphs, and Minimum Spanning Trees

202. Count Components with Union-Find

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the number of connected components after adding an undirected edge list to n initially isolated vertices. Vertices are valid indices. Repeated edges and self-loops do not create additional merges. n=0 with no edges returns zero.

Examples

Example 1

dsu_components(4,[(0,1),(1,0),(2,3)])
=> 2

The reversed repeated connection does not reduce the count again.

Example 2

dsu_components(3,[])
=> 3

Every vertex remains isolated.

Example 3

dsu_components(0,[])
=> 0

There are no initial components.

Reveal the worked solution and reasoning

Why this mechanism works

Unlike a traversal, DSU can process edges incrementally without storing adjacency. Start with n components. An edge reduces this number precisely when its endpoints currently have different representatives. Reuse the tested union contract from kata 201.

State and boundaries

dsu.count is the component count induced by the processed edge prefix.

Protocol

Create DSU(n).
Union the endpoints of every edge.
Return the maintained count.

Visualization

n=4: count 4
edge 0-1 -> 3
edge 1-0 -> still 3
edge 2-3 -> 2

Python implementation

from kata_201 import DSU

def dsu_components(n, edges):
    dsu = DSU(n)
    for a, b in edges:
        dsu.union(a, b)
    return dsu.count

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

dsu_components(4,[(0,1),(1,0),(2,3)])

L4 dsu_components: dsu = DSU(n)
n=4; edges=[(0, 1), (1, 0), (2, 3)]; dsu=DSU{'parent':[..., ..., ..., ...], 'size':[..., ..., ..., ...], 'count':4}

L5 dsu_components: for a, b in edges:
n=4; edges=[(0, 1), (1, 0), (2, 3)]; dsu=DSU{'parent':[..., ..., ..., ...], 'size':[..., ..., ..., ...], 'count':4}; a=0; b=1

L6 dsu_components: dsu.union(a, b)
n=4; edges=[(0, 1), (1, 0), (2, 3)]; dsu=DSU{'parent':[..., ..., ..., ...], 'size':[..., ..., ..., ...], 'count':3}; a=0; b=1

L5 dsu_components: for a, b in edges:
n=4; edges=[(0, 1), (1, 0), (2, 3)]; dsu=DSU{'parent':[..., ..., ..., ...], 'size':[..., ..., ..., ...], 'count':3}; a=1; b=0

L5 dsu_components: for a, b in edges:
n=4; edges=[(0, 1), (1, 0), (2, 3)]; dsu=DSU{'parent':[..., ..., ..., ...], 'size':[..., ..., ..., ...], 'count':3}; a=2; b=3

L6 dsu_components: dsu.union(a, b)
n=4; edges=[(0, 1), (1, 0), (2, 3)]; dsu=DSU{'parent':[..., ..., ..., ...], 'size':[..., ..., ..., ...], 'count':2}; a=2; b=3

Result: 2. The reversed repeated connection does not reduce the count again.

dsu_components(3,[])

L4 dsu_components: dsu = DSU(n)
n=3; edges=[]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}

Result: 3. Every vertex remains isolated.

Why the solution is correct

The empty edge prefix has n singleton components. An edge within one component leaves connectivity unchanged; an edge across two components merges exactly those two. DSU applies those cases correctly, so induction over the edge list proves the final count.

Time and space

O(n+m*alpha(n)) amortized time and O(n) auxiliary storage for m edges; no adjacency lists are required.

Common mistakes

Subtracting the number of edges from n fails when edges are redundant. Directed reachability cannot be summarized by this undirected union operation.

Reasoning card

State: dsu.count is the component count induced by the processed edge prefix.

Invariant: components changes only when two distinct roots unite.

Decision to rehearse: Union endpoints of every undirected edge.

Finish: Return the maintained count

Transfer exercise

Emit the count after each incoming edge to answer an online connectivity-progress query.