Number of Connected Components: DFS vs Union-Find

Counting connected components is the question behind a surprising number of interview problems: number of islands, friend circles, provinces, how many networks a set of cables forms, whether a graph is a valid tree. The algorithm fits in one sentence: start a fresh traversal at every node nobody has reached yet, and count the starts. The follow-ups are about the details, isolated nodes, recursion depth, and when a union-find is the better tool.

The problem it solves

You are given an undirected graph, usually as n nodes numbered 0 to n - 1 and a list of edges, and asked how many separate pieces it has. A connected component is a maximal group of nodes that can all reach each other. "Maximal" matters: you cannot add another node to the group and keep it connected.

Two properties make the counting easy:

• Every node belongs to exactly one component. Reachability in an undirected graph is symmetric and transitive, so components never overlap.
• A node with no edges is still a component, of size one. It reaches itself and nothing else.

The brute-force view, computing who can reach whom for every pair, is O(n³) with a reachability matrix. Traversal does it in O(n + m) for m edges.

The intuition

A traversal from a node, depth-first or breadth-first, visits exactly the nodes of that node's component. No more, because there are no edges out of a component; no fewer, because the traversal follows every edge it meets.

So loop over all the nodes. Each time you reach one that is not yet visited, nothing reached so far could have reached it, so it opens a region no earlier traversal touched: add one to the count and flood that region. Nodes you meet later that are already visited start nothing, which is what stops double counting. The number of fresh starts is the number of components.

Union-find gets the same count from the other direction. Start with n singleton sets, one per node, so the count is n. For each edge, merge the sets of its two endpoints; if they were in different sets, the count drops by one. Edges inside a set change nothing. It never builds an adjacency list, and it works when edges arrive one at a time and you need the count after each one.

Watch it run

The animation starts from the lesson's point: a graph need not be one piece. Six pixels, and the gaps between them are what separate one coin from another. Nobody has reached 1, so it starts a fresh sweep and adds one to the count. The sweep spreads to the touching pixel 2, which belongs to the same blob, so it is not a new component. Back in the loop, 2 was already reached by an earlier sweep, so it starts nothing new: no double counting. Nobody has reached 3, so a second sweep starts, spreading to 4 and 5. When the loop arrives at 4 and 5 they are already reached. Then 6: nobody has reached it, so a third sweep starts, and 6 touches nothing at all. A pixel that reaches only itself is still a component of size one. Three fresh starts, so three components, [1,2] [3,4,5] [6], and no idea of what a coin looks like was ever needed.

The code

The lesson's flood fill, on its six pixels:

pixels = {1: [2], 2: [1], 3: [4, 5], 4: [3], 5: [3], 6: []}

def flood(p, seen, blob):
    seen.add(p)
    blob.append(p)
    for q in pixels[p]:                  # spread to touching pixels
        if q not in seen:
            flood(q, seen, blob)
    return blob

seen, blobs = set(), []
for p in pixels:
    if p not in seen:                    # a region nobody has reached
        blobs.append(flood(p, seen, []))
print(len(blobs), blobs)                 # 3 [[1, 2], [3, 4, 5], [6]]

The usual interview form takes n and an edge list. An explicit stack avoids Python's recursion limit on a long chain of nodes:

def count_components(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)                 # undirected: both directions
    seen, count = [False] * n, 0
    for start in range(n):
        if seen[start]:
            continue
        count += 1                       # a fresh start is a new component
        seen[start] = True
        stack = [start]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True       # mark on push, never twice on the stack
                    stack.append(v)
    return count

print(count_components(5, [(0, 1), (1, 2), (3, 4)]))   # 2
print(count_components(4, []))                        # 4   every node alone
print(count_components(100000, [(i, i + 1) for i in range(99999)]))   # 1

Union-find with path halving and union by size, where the count starts at n and each successful merge removes one:

def count_components_uf(n, edges):
    parent, size, count = list(range(n)), [1] * n, n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # path halving
            x = parent[x]
        return x
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            continue                     # already one piece
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra                  # smaller tree under the larger
        size[ra] += size[rb]
        count -= 1
    return count

print(count_components_uf(5, [(0, 1), (1, 2), (3, 4)]))   # 2
print(count_components_uf(3, [(0, 1), (1, 2), (0, 2)]))   # 1   the cycle edge merges nothing

Both against brute force on 3,000 random graphs, where the brute force builds the full reachability matrix and counts the distinct rows:

import random

def brute(n, edges):
    reach = [[i == j for j in range(n)] for i in range(n)]
    for a, b in edges:
        reach[a][b] = reach[b][a] = True
    for k in range(n):                   # transitive closure
        for i in range(n):
            for j in range(n):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return len({tuple(row) for row in reach})

random.seed(20)
ok = True
for _ in range(3000):
    n = random.randint(1, 12)
    edges = [(random.randrange(n), random.randrange(n)) for _ in range(random.randint(0, 14))]
    want = brute(n, edges)
    ok &= count_components(n, edges) == want == count_components_uf(n, edges)
print(ok)                                # True

The complexity

• DFS or BFS: O(n + m) time, since every node is pushed once and every edge is looked at twice. O(n + m) space for the adjacency list and the visited marks.
• Union-find: O(m · α(n)) time for m edges, where α is the inverse Ackermann function, below 5 for any real input. O(n) space, with no adjacency list.
• Incremental edges: union-find answers "how many components now?" after each new edge in near-constant time; a traversal would have to start over.

Where it goes wrong

• Forgetting isolated nodes. Counting from the edge list alone misses every node with no edges. Loop over all n nodes.
• Adding each edge in one direction only. For an undirected graph, b must reach a too, or a traversal from b stops short and the count comes out too high.
• Deep recursion. A recursive flood on a chain of 100,000 nodes exceeds Python's default recursion limit. Use an explicit stack or a queue.
• Marking visited when popping instead of when pushing. The count stays right, but a node can sit on the stack many times.
• Applying it to a directed graph. There, reachability is one-way, and the right notion is strongly connected components.

When it shows up in interviews

It is the skeleton of number of islands, where the graph is a grid, and of friend-circle and province questions, where it is an adjacency matrix. "Is this graph a valid tree?" is one component plus exactly n - 1 edges. Interviewers often ask for both solutions and when each wins, which leads naturally into union-find with path compression. Both approaches sit side by side on the patterns cheat sheet.

How to say it in an interview

"A traversal from any node visits exactly its component, so I loop over all the nodes and start a new DFS or BFS from each one that is not yet visited, counting the starts. Isolated nodes are counted too, because the loop covers every node. I build an adjacency list with both directions and use an explicit stack to avoid recursion limits. That is O(n + m) time and space. If edges arrive over time, or I only have an edge list, I would use union-find instead: start with n components and subtract one for every edge that joins two different sets, which is near-constant time per edge."