Number of Connected Components in an Undirected Graph — Union Find / BFS

Problem Statement#

LeetCode 323 — Number of Connected Components in an Undirected Graph (Medium)

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [a, b] indicates that there is an edge between a and b in the graph.

Return the number of connected components in the graph.

Constraints:

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2, 0 <= a, b smaller than n, a != b
• No duplicate edges, no self-loops.

Example 1:

n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2 (components {0,1,2} and {3,4})

Example 2:

n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1 (single chain 0-1-2-3-4)

Why This Problem Matters#

Counting connected components is the single most common Union Find interview question at FAANG. Variants include LC 547 (Number of Provinces), LC 305 (Number of Islands II), LC 200 (Number of Islands as a graph), and LC 1971 (Find if Path Exists in Graph). Mastering this pattern unlocks an entire family of problems.

The interviewer is checking three skills:

1. Union Find fluency. Path compression and union by rank should come out of muscle memory.
2. Component counting trick. Initialize the count to n, decrement once per successful union. After all edges, the count equals the number of components.
3. BFS / DFS alternative. Equivalent O(N + E) solution; some interviewers prefer it for clarity.

This problem also generalizes cleanly to dynamic settings — adding edges one at a time and answering component-count queries online — which is a common follow-up at staff-engineer interviews.

The Core Insight#

Two equivalent approaches:

• Union Find counting. Start with count = n standalone components. Each time a union(a, b) succeeds (i.e., find(a) != find(b)), two components merge into one, so count -= 1. After processing all edges, count is the answer.
• BFS / DFS sweep. Iterate over every node. If unvisited, start a BFS / DFS from it, mark every reachable node, and increment a component counter.

Both solutions are O(N + E). Union Find is denser code but extends naturally to online queries. BFS / DFS feels more intuitive on a whiteboard. Pick whichever the interviewer signals comfort with — but be ready to write the other.

A classic trick: when you initialize count = n and decrement once per successful union, you get the answer without an explicit pass to count distinct roots at the end.

Visual Dry Run#

n = 5, edges = [[0,1],[1,2],[3,4]]. Run Union Find:

parent = [0, 1, 2, 3, 4], count = 5
 
Edge [0, 1]: find(0)=0, find(1)=1, different.
  Union -> parent = [0, 0, 2, 3, 4], count = 4.
 
Edge [1, 2]: find(1)=0, find(2)=2, different.
  Union -> parent = [0, 0, 0, 3, 4], count = 3.
 
Edge [3, 4]: find(3)=3, find(4)=4, different.
  Union -> parent = [0, 0, 0, 3, 3], count = 2.
 
Return 2. (Components: {0,1,2} and {3,4})

If we had also added [2, 0], the union would have found the same root for both, no decrement, and the answer would still be 2.

Solution (Optimal)#

Python (Union Find with path compression and union by rank)#

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        parent = list(range(n))                     # each node starts as its own root
        rank = [0] * n
        count = n                                   # n isolated components initially
 
        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]       # path compression (halving)
                x = parent[x]
            return x
 
        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False                        # already connected, no merge
            # Union by rank keeps the tree shallow
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1
            return True
 
        for a, b in edges:
            if union(a, b):
                count -= 1                          # one successful merge -> count - 1
 
        return count

JavaScript (BFS Sweep)#

/**
 * Iterate over every node; for each unvisited node, BFS its component
 * and bump the component counter.
 */
var countComponents = function(n, edges) {
    const adj = Array.from({length: n}, () => []);
    for (const [a, b] of edges) {                   // undirected adjacency list
        adj[a].push(b);
        adj[b].push(a);
    }
 
    const visited = new Array(n).fill(false);
    let components = 0;
 
    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;                   // already inside a known component
        components++;                                // start a new component
        const queue = [i];
        visited[i] = true;
        let head = 0;
        while (head < queue.length) {                // standard BFS
            const node = queue[head++];
            for (const nxt of adj[node]) {
                if (!visited[nxt]) {
                    visited[nxt] = true;
                    queue.push(nxt);
                }
            }
        }
    }
 
    return components;
};

Complexity. Union Find runs in O((N + E) alpha(N)) time, where alpha is essentially constant. BFS / DFS runs in O(N + E) time. Space is O(N) for either approach.

Common Mistakes#

1. Forgetting to start count = n. If you initialize to zero and try to "count up," you have to count distinct roots after the loop, which is more work and easier to get wrong.
2. Decrementing on every union call. Only decrement on successful unions. Calling union(0, 1) after they are already connected should be a no-op.
3. Skipping path compression. Without it, find degrades to O(N) per call on adversarial inputs and the total runtime balloons.
4. Treating the graph as directed. Edges are undirected; add both directions in the adjacency list for BFS / DFS.
5. Recursion depth in DFS. A chain of 2,000 nodes blows Python recursion stack. Use iterative BFS or bump the limit.

Interview Tips#

• Volunteer both algorithms. "I will solve this with Union Find because it generalizes to dynamic graphs, but BFS / DFS sweep is equally valid." This signals depth without hedging.
• Trace the count logic. Explicitly say "initialize count to n and decrement on every successful union." Many candidates miss this trick.
• Mention path compression and union by rank. Add a comment explaining the near-O(1) amortized cost. Interviewers grade understanding more than implementation.
• Discuss disconnected nodes. A node with no edges is its own component. Make sure your loop handles that case.

Follow-up Questions#

1. Add edges one at a time and report component count after each addition. That is exactly LC 305 (Number of Islands II). Union Find handles it incrementally.
2. Remove an edge. Plain Union Find does not support deletion. Use offline processing (reverse the operations) or link-cut trees.
3. Largest component size. Track size per root. After all unions, find the maximum size root.
4. Number of edges per component. Track edge counts per root during unions.
5. Bipartite components. Color nodes during BFS / DFS; if you ever fail to two-color, that component is not bipartite.

Key Takeaways#

• Counting components is the flagship Union Find pattern in coding interviews.
• Initialize count = n and decrement once per successful union — no extra pass needed.
• Union Find with path compression and union by rank runs in near-O(1) amortized per operation.
• BFS or DFS sweep is an equally valid O(N + E) alternative; choose by problem flavor.
• Disconnected single nodes count as their own components; loop over every node.
• The pattern generalizes to LC 547, LC 305, LC 1971, and many more graph-component questions.