Number of Connected Components in an Undirected Graph

1. Problem & Core Objective

Given n nodes labelled 0 to n − 1 and a list of undirected edges, return the number of connected components.

n = 5, edges = [[0,1],[1,2],[3,4]]   →  2      {0,1,2} and {3,4}
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]  →  1

Constraints: 1 <= n <= 2000 · 0 <= edges.length <= 5000 · no duplicate edges, no self-loops

What's actually being tested: the same component counting as Number of Islands, but on an explicit graph rather than a grid. And the union-find formulation — start with n components, decrement on each successful union — which is the cleanest statement of the idea.

2. First-Principles Thought Process

Two equally good framings

Traversal: loop over every node; if unvisited, increment the count and flood its whole component. Exactly Number of Islands, with an adjacency list instead of a grid.

Union-Find: start with n isolated components. Each edge that joins two different components reduces the count by one.

int components = n;
for (int[] e : edges)
    if (union(e[0], e[1])) components--;      // only successful unions count

Both are effectively linear. Which is better depends on what comes next.

Why the union-find framing is worth learning here

The counter starts at n and decrements — no traversal, no visited array, no adjacency list. Just an int[n].

And it makes the invariant explicit: each successful union merges two components into one, so the count drops by exactly one. An edge inside an existing component changes nothing.

The adjacency list is a real cost

The traversal approach must build List<List<Integer>> with both directions of every edge — 10,000 boxed Integer entries at the constraint limits, plus a list object per node.

Union-find needs int[2000]. For a problem this simple that's a meaningful difference in setup work.

When traversal wins

If you need the components themselves — their sizes, their members, a representative — a traversal gives them naturally. Union-find gives you the count cheaply and the membership only via a second pass calling find on every node.

3. Solution Paths

Approach 1 — DFS or BFS flood (traversal)

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]);                 // undirected — both directions
    }

    boolean[] visited = new boolean[n];
    int components = 0;

    for (int i = 0; i < n; i++)
        if (!visited[i]) { components++; dfs(adj, i, visited); }

    return components;
}

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

• Time O(V + E) · Space O(V + E) for the adjacency list

Counter-questions on this approach

⭐ "Why does the outer loop have to visit every node, not just the edge endpoints?"

Because an isolated node with no edges is still a component. With n = 5 and no edges at all, the answer is 5 — but no edge mentions any node, so iterating edges would report 0.

That's the case most easily missed: the node set matters, not just the edge list.

⭐ "Isn't a DFS inside a loop quadratic?"

No — the same amortisation as island counting. The flood only runs on an unvisited node and marks everything it reaches, so across the whole run each node is flooded exactly once. The loop and the flood add rather than multiply.

"Why add both directions to the adjacency list?"

The graph is undirected, so 0—1 must be traversable from either end. Adding one direction would make the traversal miss components reachable only "backwards".

"What's the stack depth?"

Up to n = 2000 on a path graph — safe. At 10^5 I'd use BFS or an explicit stack.

Approach 2 — Union-Find (optimal)

public int countComponents(int n, int[][] edges) {
    int[] parent = new int[n];
    int[] size = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }

    int components = n;                          // every node starts alone

    for (int[] e : edges) {
        int a = find(parent, e[0]), b = find(parent, e[1]);
        if (a == b) continue;                    // already together — no change

        if (size[a] < size[b]) { int t = a; a = b; b = t; }   // union by size
        parent[b] = a;
        size[a] += size[b];
        components--;                             // two components became one
    }
    return components;
}

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

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

• Time O(E · α(n)) · Space O(n)

Counter-questions on this approach

⭐ "Why start at n and decrement rather than counting roots at the end?"

Both work. Decrementing maintains the count incrementally, so the answer is ready the moment the last edge is processed — no final pass.

Counting roots afterwards means calling find on all n nodes, which is another O(n · α). Trivial here, but the decrement is both cheaper and a clearer statement of the invariant: each successful union merges two components into one.

⭐ "What does find(a) == find(b) mean here, and why skip?"

They're already in the same component, so this edge adds no connectivity — it's a redundant edge within a component, which in question 10 would have been a cycle. Here cycles are allowed; they just don't change the count.

That's the difference between this problem and Graph Valid Tree: there a == b is a rejection, here it's a no-op.

⭐ "Explain path compression and union by size — are they the same optimisation?"

No, they're independent and both are usually included.

Union by size attaches the smaller tree under the larger root, which stops a long chain forming in the first place — it bounds the depth at O(log n).

Path compression flattens the path on every find, re-pointing each node on the way directly at the root.

Either alone gives O(log n) amortised; together they give O(α(n)), where α is the inverse Ackermann function — below 5 for any n that fits in the universe. Effectively constant, though I'd say "effectively" rather than claiming O(1).

"Why swap so the larger tree is the root?"

Attaching the smaller under the larger keeps the resulting tree's depth from growing: the merged tree's depth is the larger tree's depth unless the smaller was deeper. Doing it the other way round can create a chain, which is exactly what union-by-size prevents.

"What if there are no edges?"

The loop never runs and components stays n — correct, since every node is its own component. That's the case the traversal approach must handle with an explicit loop over all nodes; here it's the initial value.

"Can find overflow the stack?"

With union by size the depth is O(log n) ≈ 11 at n = 2000, so no. Without it, an adversarial union order could build a 2000-deep chain. An iterative find removes the concern entirely.

Comparison

4. Why the Optimal Wins

Both are effectively linear, so the difference is setup and what you get out.

Union-find needs a single int[n] — no adjacency list, no visited array, no traversal. At 5000 edges the traversal approach allocates 10,000 boxed Integers plus 2000 list objects before doing any work.

And the invariant is clean: start at n, decrement on each successful union. Redundant edges are a no-op, which is exactly what "doesn't change connectivity" should look like in code.

The traversal wins if you need the components themselves rather than just the count.

The framing worth keeping:

Start with n components and decrement on every union that actually merges. An edge inside an existing component changes nothing — which is the same test that means "cycle" in Graph Valid Tree, reinterpreted.

5. Java Prerequisites

Union-Find with both optimisations

int[] parent = new int[n], size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }

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

boolean union(int x, int y) {
    int a = find(x), b = find(y);
    if (a == b) return false;                          // already together
    if (size[a] < size[b]) { int t = a; a = b; b = t; } // union by size
    parent[b] = a; size[a] += size[b];
    return true;
}

The component counter — int components = n; then if (union(...)) components--;

Undirected adjacency for the traversal version — both directions per edge.

α(n) — inverse Ackermann, below 5 for any practical n. Say "effectively constant", not O(1).

6. Interview Communication Guide

Clarifying questions: Are edges undirected (yes)? Do isolated nodes count as components (yes — this is the trap)? Can there be duplicate edges (no, but union-find handles them anyway)? Is n guaranteed positive (yes)?

The pitch

"Two good framings, and I'd mention both.

The traversal version is island counting on an explicit graph: loop over all n nodes, and when you find an unvisited one, increment the count and flood its component. The key detail is looping over nodes, not edges — an isolated node with no edges is still a component, so n = 5 with no edges is 5, and iterating edges would report 0.

The union-find version is cleaner here. Start with n components — every node alone — and for each edge, if its endpoints are in different components, merge them and decrement. If they're already together, the edge adds no connectivity and nothing changes.

That makes the invariant explicit: each successful union merges two components into one, so the count drops by exactly one.

I'd prefer it because it needs only an int[n]. The traversal version has to build an adjacency list with both directions of every edge — 10,000 boxed entries at these limits — before doing any work.

With path compression and union by size it's O(E · α(n)), effectively linear. Those two are independent optimisations: union by size stops deep chains forming, path compression flattens whatever chains exist. Either alone gives O(log n); together, O(α(n)).

The 'no edges' case is handled by the initial value — components starts at n and nothing decrements it.

I'd switch to traversal if I needed the components themselves rather than just the count, since union-find only gives membership via a second pass."

Edge cases to volunteer:

Name the no-edges case and the triangle. The first is what the node loop (or the initial n) exists for; the second confirms that redundant edges are a no-op, not an error — the opposite of their meaning in Graph Valid Tree.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the size of the largest component."

Union by size already tracks it — after processing every edge, take the maximum size[i] over all roots. Free, because the optimisation and the answer need the same data.

⭐ "Edges are added one at a time; report the count after each."

This is where union-find decisively beats traversal: each addition is O(α) and updates the count incrementally. Re-running a traversal per edge would be O(E · (V + E)).

Deletion, however, is genuinely hard — union-find has no undo. You'd need a link-cut tree or offline processing in reverse.

"Return the components themselves, not the count."

Second pass: group nodes by find(i) into a Map<Integer, List<Integer>>. O(n · α). Or just use the traversal version, which produces them naturally.

"What if the graph were directed?"

"Connected component" becomes ambiguous — weakly connected (ignore direction, so this algorithm works unchanged) or strongly connected (every node reaches every other, needing Tarjan's or Kosaraju's at O(V + E)). Worth asking which is meant rather than assuming.

"What if n were 10^6 with 10^7 edges?"

Union-find scales fine — int[10^6] is 4 MB. I'd make find iterative to avoid deep recursion. The traversal version's adjacency list would be 10 million boxed Integers, which is where it becomes impractical.

"Count components in a grid instead of an explicit graph."

That's Number of Islands. Flatten (r, c) to r * n + c and union adjacent land cells — the same code with a different neighbour rule.