Number of Connected Components in an Undirected Graph

MediumGraphs · Union-Find · DFS🧩 Union-Find LeetCode #323 ↗Updated Oct 30, 2026

Problem

You have n nodes labelled 0..n-1 and a list of undirected edges, where [a, b] joins nodes a and b. Return how many connected components the graph has — i.e. how many separate “islands” of nodes remain, counting isolated nodes as their own island.

Inputn=5, edges=[[0,1],[1,2],[3,4]]Output2

Inputn=5, edges=[[0,1],[1,2],[2,3],[3,4]]Output1

Inputn=4, edges=[]Output4

1 ≤ n ≤ 2000 · 0 ≤ edges.length ≤ 5000 · a ≠ b · no repeated edges

Try it yourself

Java

class Solution {
    public int countComponents(int n, int[][] edges) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Start with n separate components. Every edge that joins two different components merges them, so the answer is n minus the number of successful merges — exactly what Union-Find counts.

PatternUnion-Find

Instinct Items get grouped by "connected", "same as" or "shares a" links and you keep asking which group something is in: merge sets with Union-Find.

Memory hack Find your boss, merge the bosses; squash the chain (path compression) and hang the short tree under the tall one (rank).

Open the Union-Find guide →

Approaches

Brute ForceLabel Propagation Until Stable

Time O(V · E)Space O(V)

Give every node its own label. Repeatedly sweep the edge list and let both ends adopt the smaller label. The minimum label spreads one hop per sweep, so after at most V sweeps every component carries its smallest node id; count nodes whose label is still their own id.

Java

public int countComponents(int n, int[][] edges) {
    int[] label = new int[n];
    for (int i = 0; i < n; i++) label[i] = i;
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int[] e : edges) {
            int m = Math.min(label[e[0]], label[e[1]]);
            if (label[e[0]] != m || label[e[1]] != m) {
                label[e[0]] = m;
                label[e[1]] = m;
                changed = true;
            }
        }
    }
    // Each component ends up labelled with its smallest node id
    int count = 0;
    for (int i = 0; i < n; i++) if (label[i] == i) count++;
    return count;
}

No graph structure needed, but up to V full passes over the edges.

BetterAdjacency List + DFS Flood Fill

Time O(V + E)Space O(V + E)

Build an adjacency list. Scan nodes; each unvisited node starts a new component, and an iterative DFS marks everything reachable from it. Every node and edge is touched a constant number of times.

Java

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) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    boolean[] seen = new boolean[n];
    int count = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        count++; // new island found
        seen[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : adj.get(u)) {
                if (!seen[v]) {
                    seen[v] = true;
                    stack.push(v);
                }
            }
        }
    }
    return count;
}

Linear time, but must materialise the whole adjacency list first.

OptimalUnion-Find (Path Compression + Union by Size)

Time O(V + E · α(V))Space O(V)

Keep a parent array where each component has one root. For every edge find both roots; if they differ, link the smaller tree under the larger and decrement the component count. Path compression keeps trees almost flat, so each operation is effectively constant.

Java

private int[] parent, size;

public int countComponents(int n, int[][] edges) {
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    int components = n;
    for (int[] e : edges) {
        if (union(e[0], e[1])) components--;
    }
    return components;
}

private int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // path halving
        x = parent[x];
    }
    return x;
}

private boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false; // already connected
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;
    size[ra] += size[rb];
    return true;
}

Near-linear, only O(V) memory, and works when edges arrive as a stream.

Pro tip

Say the invariant aloud: components = n − (edges that joined two different roots). Edges inside a component (cycles) change nothing.

At a glance

Level	Approach	Time	Space
Brute Force	Label Propagation Until Stable	`O(V · E)`	`O(V)`
Better	Adjacency List + DFS Flood Fill	`O(V + E)`	`O(V + E)`
Optimal	Union-Find (Path Compression + Union by Size)	`O(V + E · α(V))`	`O(V)`

Common pitfalls

Forgetting isolated nodes — a node with no edges is still one component.
Decrementing the count on every edge — edges that close a cycle must not count.
Adding only one direction to the adjacency list — the graph is undirected.

Interview tips

Mention both DFS and Union-Find; pick Union-Find if edges could arrive incrementally.
Explain why path compression + union by size gives near-constant amortised cost.
Use an iterative stack for DFS to avoid deep recursion on a long chain.

Pattern

Union-Find / flood fill → counting or merging groups of connected items.

My notes saved in this browser