323. Number of Connected Components in an Undirected Graph

Counting connected components is the problem that finally makes Union-Find click — you watch a running counter drop by one every time two groups fuse, and the whole data structure stops feeling abstract. It sits in the graph traversal pattern alongside island counting and cycle detection, and the counting trick here carries straight over to those.

The problem

You have n nodes labeled 0 through n-1 and a list of undirected edges. Report how many separate groups the nodes fall into, where a group is any set of nodes you can walk between by following edges. (Full statement on LeetCode.)

With n = 5 and edges [[0,1],[1,2],[3,4]], node 0-1-2 form one clump and 3-4 form another, so the answer is 2.

Intuition: count the merges, not the nodes

Start from the extreme case: with zero edges, every node stands alone, so there are exactly n components. Now feed edges in one at a time. An edge either connects two nodes that already share a group — in which case nothing changes — or it bridges two separate groups and fuses them into one, dropping the count by exactly one.

So the answer is just:

$\text{components} = n - (\text{number of edges that joined two distinct groups})$

That reframing is why Union-Find fits so well. It’s built to answer one question fast — “are these two nodes already in the same set?” — and to merge two sets when they aren’t. find(x) walks up to the representative root of x’s set; if two endpoints have different roots, they were separate, so union them and decrement. The two optimizations, path compression in find and union by rank in union, keep each operation at roughly constant amortized cost, $O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function — effectively a small constant for any input you’ll ever see.

Solution

Union-Find first, since it maps directly onto the counting idea:

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;  // each node is its own root

        int components = n;                          // start fully disconnected
        for (int[] e : edges) {
            int ra = find(parent, e[0]);
            int rb = find(parent, e[1]);
            if (ra != rb) {                          // edge bridges two groups
                union(parent, rank, ra, rb);
                components--;
            }
        }
        return components;
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);     // path compression
        }
        return parent[x];
    }

    private void union(int[] parent, int[] rank, int ra, int rb) {
        if (rank[ra] < rank[rb]) {                   // attach shorter tree under taller
            parent[ra] = rb;
        } else if (rank[ra] > rank[rb]) {
            parent[rb] = ra;
        } else {
            parent[rb] = ra;
            rank[ra]++;
        }
    }
}

If Union-Find isn’t in your toolbox yet, plain DFS flood fill gets the same answer: build an adjacency list, then start a traversal from every node you haven’t visited. Each fresh start is one new component.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {                      // undirected: link both ways
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        boolean[] seen = new boolean[n];
        int components = 0;
        for (int i = 0; i < n; i++) {
            if (!seen[i]) {                          // untouched node = new component
                dfs(adj, seen, i);
                components++;
            }
        }
        return components;
    }

    private void dfs(List<List<Integer>> adj, boolean[] seen, int node) {
        seen[node] = true;
        for (int next : adj.get(node)) {
            if (!seen[next]) dfs(adj, seen, next);
        }
    }
}

Complexity

Approach	Time	Space
Union-Find (compression + rank)	$O((V + E)\,\alpha(n))$	$O(V)$
DFS flood fill	$O(V + E)$	$O(V + E)$

Both are effectively linear. Union-Find wins on space because it never materializes an adjacency list — just two integer arrays — and it’s the more natural fit if edges arrive as a stream rather than all at once.

In an interview

Say the counting invariant out loud before you code: “I’ll start with n components and subtract one each time an edge joins two groups that weren’t already connected.” That single sentence tells the interviewer you understand why Union-Find applies, not just that you memorized it. The trap to name is the ra != rb guard — decrement only when the roots differ. Drop that check and a redundant edge inside an existing group wrongly lowers your count. If you’d rather traverse, DFS or BFS is fully accepted here; the only Union-Find-specific gotcha is the balancing. Union by rank is what guarantees the height bound — it caps trees at $O(\log n)$ tall — and path compression then flattens them toward near-constant amortized time. Drop the rank and even with compression a bad union order can build a linear chain that a find walks before it ever gets compressed, so both pull their weight.

This same “one traversal per unvisited node” counting shows up in Number of Islands, and adding a cycle check to this exact scaffold gives you Graph Valid Tree. The graph pattern hub lays out where each variation diverges.

References

• LeetCode 323 — Number of Connected Components in an Undirected Graph