Number of Connected Components in an Undirected Graph (LC 323)

Pattern: Union-Find (DSU) or DFS/BFS component count
Difficulty: Medium (Premium; Blind 75 staple)
Key Concept: Start with n isolated nodes; each edge merges two components — track how many components remain, or count DFS/BFS launches from unvisited nodes.

Problem Statement

You have n nodes labeled 0 to n-1 and a list of undirected edges edges[i] = [a, b].

Return the number of connected components in the graph.

Input: int n, int[][] edges
Output: int

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

---

1. Algorithm & Pseudocode

Brute force

Repeatedly scan all edges to merge labels (naive “connected components via repeated relaxation”) — O(n·m) or worse.

Or: build adjacency matrix n×n and DFS — O(n²) memory if dense.

Optimal

Union-Find

components = n
parent[i] = i
for (u,v) in edges:
  if find(u) != find(v):
    union(u,v)
    components--

return components

DFS

build adjacency lists
visited[0..n-1] = false
count = 0
for i in 0..n-1:
  if !visited[i]:
    count++
    dfs(i)

return count

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Component = maximal set of nodes mutually reachable.
• Union-Find: Think of each node as its own set; union shrinks the number of sets when it actually merges two different roots.
• DFS count: Each time you meet an unvisited node, you are entering a new island of the graph.

---

3. The Dry Run

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

Union-Find

Step	Edge	Same set already?	components
init	—	—	5
1	0-1	no	4
2	1-2	no	3
3	0-2	yes (already connected)	3
4	3-4	no	2

Answer 2 (component {0,1,2} and {3,4}).

---

4. Java Solution

Brute Force

Adjacency matrix + DFS (wastes space when sparse):

class SolutionBrute {
    public int countComponents(int n, int[][] edges) {
        boolean[][] g = new boolean[n][n];
        for (int[] e : edges) {
            g[e[0]][e[1]] = g[e[1]][e[0]] = true;
        }
        boolean[] vis = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ans++;
                dfs(i, g, vis);
            }
        }
        return ans;
    }

    private void dfs(int u, boolean[][] g, boolean[] vis) {
        vis[u] = true;
        for (int v = 0; v < g.length; v++) {
            if (g[u][v] && !vis[v]) dfs(v, g, vis);
        }
    }
}

Time: O(n²) scan per DFS wave in worst case, Space: O(n²).

Optimal

DSU

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

        int comps = n;
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            int pu = find(parent, u), pv = find(parent, v);
            if (pu != pv) {
                parent[pu] = pv;
                comps--;
            }
        }
        return comps;
    }

    private int find(int[] p, int x) {
        if (p[x] != x) p[x] = find(p, p[x]);
        return p[x];
    }
}

DFS with adjacency lists

import java.util.*;

class SolutionDFS {
    public int countComponents(int n, int[][] edges) {
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) {
            adj[e[0]].add(e[1]);
            adj[e[1]].add(e[0]);
        }
        boolean[] vis = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ans++;
                Deque<Integer> st = new ArrayDeque<>();
                st.push(i);
                while (!st.isEmpty()) {
                    int u = st.pop();
                    if (vis[u]) continue;
                    vis[u] = true;
                    for (int v : adj[u]) if (!vis[v]) st.push(v);
                }
            }
        }
        return ans;
    }
}

Time: O(n + m) where m = edges.length, Space: O(n + m) for adjacency + stack, or O(n) for DSU parent array.

---

5. The “Java vs. Others” Edge

• DSU shines when edges arrive as a stream (dynamic connectivity).
• Recursive DFS can hit stack limits on long chains; iterative ArrayDeque is safer on JVM for deep graphs.
• Use List<Integer>[] for sparse graphs — avoid O(n²) matrix unless n is tiny.

---

6. Complexity Summary

Approach	Time	Space	Notes
Matrix + DFS	O(n²)	O(n²)	Poor for sparse
Adjacency + DFS/BFS	O(n + m)	O(n + m)	Clear for static graph
Union-Find	O(n + m α(n))	O(n)	Great for counting merges

---

ASCII: Components

n=6, edges: 0-1, 1-2,   3-4,   5 alone

  0---1---2      3---4      5

3 components: [0,1,2], [3,4], [5]