Number of Connected Components (LeetCode 323)

The problem

You get n nodes labelled 0 to n - 1 and a list of undirected edges. Return how many connected components the graph has: groups of nodes where you can walk from any node to any other in the group.

Input:  n = 5, edges = [[0,1], [1,2], [3,4]]
Output: 2

Nodes 0, 1 and 2 are linked into one group; 3 and 4 form another.

How to think about it

Start with brute force. For each pair of nodes, run a search to see whether they’re connected, then group them. That’s O(n²) searches, each O(n + E). Far too much repeated work.

A good linear answer: flood fill. Build an adjacency list, then scan the nodes. Each unvisited node starts a DFS or BFS that marks its whole component, and you add one to the count. That’s exactly Number of Islands on a general graph, and it runs in O(V + E). It’s a perfectly good answer.

The key insight for union-find: every useful edge merges two groups. Start with n components, one per node. Process the edges one at a time. If an edge joins two nodes that are already in the same group, nothing changes. If it joins two different groups, they merge and the count drops by one. After all edges, the count is the answer. You never build an adjacency list, and it works just as well if edges arrive as a stream.

Which pattern is this? Union-find (disjoint set union). The tell is “count groups / are these connected?” on an undirected graph, especially when edges arrive one at a time. find(x) walks up to the group’s root; path compression (parent[x] = parent[parent[x]]) keeps the trees flat so each call is nearly O(1).

Approach

1. Set parent[i] = i for every node: n groups of one.
2. find(x) follows parents to the root, halving the path as it goes.
3. Start comp = n. For each edge (a, b), find both roots.
4. If the roots differ, link one to the other and decrease comp.
5. Return comp.

Solution

def count_components(n, edges):
    parent = list(range(n))                    # every node starts as its own group
    def find(x):
        while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]   # path halving
        return x
    comp = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb: parent[ra] = rb; comp -= 1   # two groups merge into one
    return comp
# count_components(5, [[0,1],[1,2],[3,4]]) -> 2

Dry run

On n = 5, edges = [[0,1],[1,2],[3,4]]:

Three merges from five singletons leaves 2 components. With an extra edge (0, 2), both ends would find root 2, so no merge and no change.

Complexity

• Time: O(V + E·α(V)). Setting up parent is O(V), and each edge does two find calls. With path compression, each is amortised close to O(1); α is the inverse Ackermann function, under 5 for any real input. (Adding union by rank as well guarantees the α bound.)
• Space: O(V) for the parent array.

Edge cases and pitfalls

• No edges returns n: every node is alone.
• Isolated nodes count as components. That’s why you start at n instead of counting from the edges.
• Redundant edges (a cycle, or a duplicate edge) don’t change the count, because both ends already share a root.
• Comparing parent[a] != parent[b] instead of the roots. Parents can differ while the roots are the same. Always compare find(a) and find(b).
• Recursive find can hit Python’s recursion limit on a long chain if compression hasn’t kicked in. The iterative loop avoids that.

Related problems

• Number of Islands (LeetCode 200): the same question on a grid, solved with flood fill.
• Graph Valid Tree (LeetCode 261): a tree is exactly one component with no redundant edges.
• Redundant Connection (LeetCode 684): find the first edge whose ends already share a root.