#48 · Graphs

Number of Connected Components in an Undirected Graph

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

MediumLeetCode

Current
On path / queued
Done
Cycle / blocked

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Adjacency list

For each node, the list of its neighbours. It stores only edges that exist, so n nodes and e edges take O(n + e) memory, and visiting all neighbours of a node costs its degree.

Memory layout

An array of n dynamic arrays; each edge appears twice for an undirected graph.

Operation	Cost
build	O(n + e)
visit all neighbours of v	O(deg(v))

Union-Find (disjoint set union)

A partition of the nodes into sets. Each edge merges the sets of its two endpoints; the number of components is the number of sets left. No traversal is needed, and edges can arrive in any order or one at a time.

Memory layout

parent[] (and optionally size[]) integer arrays of length n.

Operation	Cost
find / union	O(α(n)), practically constant

Why it fits

A connected component is a maximal set of nodes joined by paths. A search from any node reaches exactly its component, so counting how many searches you start counts components.
Union-Find tracks the same partition incrementally: it starts with n components and every successful merge removes exactly one.
Both approaches touch each node and edge a near-constant number of times, so they are linear (or almost) in the input size.

Why alternatives degrade

Adjacency matrix:: It needs n² memory and an O(n) scan of a row to find a node's neighbours, so DFS becomes O(n²) even for very sparse graphs.
Counting edges:: The number of edges does not determine the components: 3 edges can form a path of 4 nodes or a triangle plus 3 isolated nodes.
Sorting the edge list:: Order does not reveal connectivity; you still need to track which nodes are linked.

Four approaches, from naive to production

1 · beginner

Adjacency matrix + DFS

time O(n²)space O(n²)

Store the graph in an n × n table of booleans. For each unvisited node, start a depth-first search that scans a row of the table to find neighbours; each search marks one whole component.

int countComponents(int n, vector<vector<int>>& edges) {
    vector<vector<bool>> matrix(n, vector<bool>(n, false));
    for (auto& e : edges) {
        matrix[e[0]][e[1]] = true;
        matrix[e[1]][e[0]] = true;
    }
    vector<bool> visited(n, false);
    function<void(int)> dfs = [&](int node) {
        visited[node] = true;
        for (int next = 0; next < n; next++) {
            if (matrix[node][next] && !visited[next]) dfs(next);
        }
    };
    int count = 0;
    for (int node = 0; node < n; node++) {
        if (!visited[node]) {
            dfs(node);
            count++;
        }
    }
    return count;
}

public int countComponents(int n, int[][] edges) {
    boolean[][] matrix = new boolean[n][n];
    for (int[] e : edges) {
        matrix[e[0]][e[1]] = true;
        matrix[e[1]][e[0]] = true;
    }
    boolean[] visited = new boolean[n];
    int count = 0;
    for (int node = 0; node < n; node++) {
        if (!visited[node]) {
            dfs(matrix, visited, node);
            count++;
        }
    }
    return count;
}
private void dfs(boolean[][] matrix, boolean[] visited, int node) {
    visited[node] = true;
    for (int next = 0; next < matrix.length; next++) {
        if (matrix[node][next] && !visited[next]) dfs(matrix, visited, next);
    }
}

def count_components(n, edges):
    matrix = [[False] * n for _ in range(n)]
    for a, b in edges:
        matrix[a][b] = True
        matrix[b][a] = True
    visited = [False] * n
    def dfs(node):
        visited[node] = True
        for nxt in range(n):
            if matrix[node][nxt] and not visited[nxt]: dfs(nxt)
    count = 0
    for node in range(n):
        if not visited[node]:
            dfs(node)
            count += 1
    return count

function countComponents(n: number, edges: number[][]): number {
  const matrix: boolean[][] = Array.from({ length: n }, () => new Array<boolean>(n).fill(false));
  for (const [a, b] of edges) {
    matrix[a][b] = true;
    matrix[b][a] = true;
  }
  const visited = new Array<boolean>(n).fill(false);
  const dfs = (node: number): void => {
    visited[node] = true;
    for (let next = 0; next < n; next++) {
      if (matrix[node][next] && !visited[next]) dfs(next);
    }
  };
  let count = 0;
  for (let node = 0; node < n; node++) {
    if (!visited[node]) {
      dfs(node);
      count++;
    }
  }
  return count;
}

Flaws & bottlenecks

The table uses n² cells even when there are few edges.
Finding the neighbours of a node means scanning an entire row of n entries.
Recursion depth can reach n on a long path.

Interviewer cross-questions

When is a matrix a good choice?

Say: For dense graphs (about n² edges) or when you need a constant-time "is there an edge between a and b?" test. For sparse graphs it wastes both memory and time.

Why count searches?

Say: One DFS reaches exactly the nodes of one component. Any node still unvisited afterwards is in a different component, so each new start is a new component.

How do you improve the time?

Say: Use an adjacency list so visiting neighbours costs the node's degree, making the total O(n + e).

2 · intermediate

Adjacency list + BFS

time O(n + e)space O(n + e)

Build an adjacency list. For each unvisited node, count a component and run a breadth-first search with a queue, marking nodes as they are queued so none is queued twice.

int countComponents(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<bool> visited(n, false);
    int count = 0;
    for (int start = 0; start < n; start++) {
        if (visited[start]) continue;
        count++;
        visited[start] = true;
        vector<int> queue = {start};
        size_t head = 0;
        while (head < queue.size()) {
            int node = queue[head++];
            for (int next : adj[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.push_back(next);
                }
            }
        }
    }
    return count;
}

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[] visited = new boolean[n];
    int count = 0;
    for (int start = 0; start < n; start++) {
        if (visited[start]) continue;
        count++;
        visited[start] = true;
        List<Integer> queue = new ArrayList<>(); queue.add(start);
        int head = 0;
        while (head < queue.size()) {
            int node = queue.get(head++);
            for (int next : adj.get(node)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
    return count;
}

def count_components(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = [False] * n
    count = 0
    for start in range(n):
        if visited[start]: continue
        count += 1
        visited[start] = True
        queue = [start]
        head = 0
        while head < len(queue):
            node = queue[head]
            head += 1
            for nxt in adj[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    queue.append(nxt)
    return count

function countComponents(n: number, edges: number[][]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Array<boolean>(n).fill(false);
  let count = 0;
  for (let start = 0; start < n; start++) {
    if (visited[start]) continue;
    count++;
    visited[start] = true;
    const queue: number[] = [start];
    let head = 0;
    while (head < queue.length) {
      const node = queue[head++];
      for (const next of adj[node]) {
        if (!visited[next]) {
          visited[next] = true;
          queue.push(next);
        }
      }
    }
  }
  return count;
}

Flaws & bottlenecks

Builds an adjacency list first (extra O(e) memory and a pass over the edges).
Does not handle edges that arrive over time without recomputing.
Must be careful to mark a node visited when queued, not when dequeued, or it can be queued several times.

Interviewer cross-questions

BFS or DFS here?

Say: Either is fine: both find the whole component. BFS uses a queue and no recursion, so there is no depth limit.

What is the complexity?

Say: Every node is queued once and every adjacency list entry is looked at once: O(n + e).

What if edges stream in one by one?

Say: Use Union-Find: each new edge is merged in near-constant time and the component count updates immediately.

3 · advanced

Union-Find with a counter

time O(n + e · α(n))space O(n)

Start with every node in its own set and count = n. For each edge, find the leaders of both ends; if they differ, merge the sets and decrease the count. The count at the end is the number of components.

int countComponents(int n, vector<vector<int>>& edges) {
    vector<int> parent(n); iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) -> int {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    };
    int count = n;
    for (auto& e : edges) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra != rb) {
            parent[ra] = rb;
            count--;
        }
    }
    return count;
}

public int countComponents(int n, int[][] edges) {
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int count = n;
    for (int[] e : edges) {
        int ra = find(parent, e[0]), rb = find(parent, e[1]);
        if (ra != rb) {
            parent[ra] = rb;
            count--;
        }
    }
    return count;
}
private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

def count_components(n, edges):
    parent = list(range(n))
    def find(x):
        if parent[x] != x: parent[x] = find(parent[x])
        return parent[x]
    count = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            count -= 1
    return count

function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  let count = n;
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) {
      parent[ra] = rb;
      count--;
    }
  }
  return count;
}

Flaws & bottlenecks

The recursive find could go deep on a long chain before compression (use an iterative find for huge inputs).
Merging without union by size can create tall trees early.
It tells you how many components there are, but not their members, without another pass.

Interviewer cross-questions

Why does count start at n?

Say: With no edges every node is its own component. Each edge that joins two different components reduces the number by exactly one.

Why does an edge inside one component not change the count?

Say: Both ends have the same leader, so no sets are merged: the edge adds a cycle, not a new connection.

When is Union-Find better than DFS?

Say: When edges are added over time (dynamic connectivity) or when you do not want to build an adjacency list at all.

4 · expert

Union by size, path halving, early exit

time O(n + e · α(n))space O(n)

Union-Find over flat integer arrays. find halves paths iteratively; each merge attaches the smaller set under the bigger one; and the loop stops as soon as a single component remains.

int countComponents(int n, vector<vector<int>>& edges) {
    vector<int> parent(n);
    vector<int> size(n, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    auto find = [&](int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    int count = n;
    for (int i = 0; i < (int)edges.size() && count > 1; i++) {
        int a = find(edges[i][0]), b = find(edges[i][1]);
        if (a == b) continue;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        count--;
    }
    return count;
}

public int countComponents(int n, int[][] edges) {
    int[] parent = new int[n];
    int[] size = new int[n];
    Arrays.fill(size, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    int count = n;
    for (int i = 0; i < edges.length && count > 1; i++) {
        int a = find(parent, edges[i][0]), b = find(parent, edges[i][1]);
        if (a == b) continue;
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        size[a] += size[b];
        count--;
    }
    return count;
}
private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

def count_components(n, edges):
    parent = list(range(n))
    size = [1] * n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    count = n
    for i in range(len(edges)):
        if count <= 1: break
        a, b = find(edges[i][0]), find(edges[i][1])
        if a == b: continue
        if size[a] < size[b]: a, b = b, a
        parent[b] = a
        size[a] += size[b]
        count -= 1
    return count

function countComponents(n: number, edges: number[][]): number {
  const parent = new Int32Array(n);
  const size = new Int32Array(n).fill(1);
  for (let i = 0; i < n; i++) parent[i] = i;
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };
  let count = n;
  for (let i = 0; i < edges.length && count > 1; i++) {
    let a = find(edges[i][0]), b = find(edges[i][1]);
    if (a === b) continue;
    if (size[a] < size[b]) [a, b] = [b, a];
    parent[b] = a;
    size[a] += size[b];
    count--;
  }
  return count;
}

Flaws & bottlenecks

More moving parts (two arrays, swap, early exit) than the plain version.
The early exit only helps when the graph becomes fully connected before the edges run out.
Assumes every endpoint is a valid index 0 … n − 1.

Interviewer cross-questions

Why does the early exit work?

Say: The count can never go below 1, so once it is 1 every remaining edge would join nodes that are already connected.

Why union by size?

Say: It bounds tree height by log n, which keeps finds fast even without compression, and together with path halving gives near-constant amortized cost.

What changes if n can be huge but edges are few?

Say: The arrays are still size n. If only touched nodes matter, use a hash map for parent and size, creating entries lazily, and count components as (distinct nodes − merges) plus isolated ones.

Synchronized code walkthrough

Showing: Adjacency matrix + DFS — shares the player above; click any step to jump.

int countComponents(int n, vector<vector<int>>& edges) {
    vector<vector<bool>> matrix(n, vector<bool>(n, false));
    for (auto& e : edges) {
        matrix[e[0]][e[1]] = true;
        matrix[e[1]][e[0]] = true;
    }
    vector<bool> visited(n, false);
    function<void(int)> dfs = [&](int node) {
        visited[node] = true;
        for (int next = 0; next < n; next++) {
            if (matrix[node][next] && !visited[next]) dfs(next);
        }
    };
    int count = 0;
    for (int node = 0; node < n; node++) {
        if (!visited[node]) {
            dfs(node);
            count++;
        }
    }
    return count;
}

public int countComponents(int n, int[][] edges) {
    boolean[][] matrix = new boolean[n][n];
    for (int[] e : edges) {
        matrix[e[0]][e[1]] = true;
        matrix[e[1]][e[0]] = true;
    }
    boolean[] visited = new boolean[n];
    int count = 0;
    for (int node = 0; node < n; node++) {
        if (!visited[node]) {
            dfs(matrix, visited, node);
            count++;
        }
    }
    return count;
}
private void dfs(boolean[][] matrix, boolean[] visited, int node) {
    visited[node] = true;
    for (int next = 0; next < matrix.length; next++) {
        if (matrix[node][next] && !visited[next]) dfs(matrix, visited, next);
    }
}

def count_components(n, edges):
    matrix = [[False] * n for _ in range(n)]
    for a, b in edges:
        matrix[a][b] = True
        matrix[b][a] = True
    visited = [False] * n
    def dfs(node):
        visited[node] = True
        for nxt in range(n):
            if matrix[node][nxt] and not visited[nxt]: dfs(nxt)
    count = 0
    for node in range(n):
        if not visited[node]:
            dfs(node)
            count += 1
    return count

function countComponents(n: number, edges: number[][]): number {
  const matrix: boolean[][] = Array.from({ length: n }, () => new Array<boolean>(n).fill(false));
  for (const [a, b] of edges) {
    matrix[a][b] = true;
    matrix[b][a] = true;
  }
  const visited = new Array<boolean>(n).fill(false);
  const dfs = (node: number): void => {
    visited[node] = true;
    for (let next = 0; next < n; next++) {
      if (matrix[node][next] && !visited[next]) dfs(next);
    }
  };
  let count = 0;
  for (let node = 0; node < n; node++) {
    if (!visited[node]) {
      dfs(node);
      count++;
    }
  }
  return count;
}

int countComponents(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<bool> visited(n, false);
    int count = 0;
    for (int start = 0; start < n; start++) {
        if (visited[start]) continue;
        count++;
        visited[start] = true;
        vector<int> queue = {start};
        size_t head = 0;
        while (head < queue.size()) {
            int node = queue[head++];
            for (int next : adj[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.push_back(next);
                }
            }
        }
    }
    return count;
}

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[] visited = new boolean[n];
    int count = 0;
    for (int start = 0; start < n; start++) {
        if (visited[start]) continue;
        count++;
        visited[start] = true;
        List<Integer> queue = new ArrayList<>(); queue.add(start);
        int head = 0;
        while (head < queue.size()) {
            int node = queue.get(head++);
            for (int next : adj.get(node)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
    return count;
}

def count_components(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = [False] * n
    count = 0
    for start in range(n):
        if visited[start]: continue
        count += 1
        visited[start] = True
        queue = [start]
        head = 0
        while head < len(queue):
            node = queue[head]
            head += 1
            for nxt in adj[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    queue.append(nxt)
    return count

function countComponents(n: number, edges: number[][]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Array<boolean>(n).fill(false);
  let count = 0;
  for (let start = 0; start < n; start++) {
    if (visited[start]) continue;
    count++;
    visited[start] = true;
    const queue: number[] = [start];
    let head = 0;
    while (head < queue.length) {
      const node = queue[head++];
      for (const next of adj[node]) {
        if (!visited[next]) {
          visited[next] = true;
          queue.push(next);
        }
      }
    }
  }
  return count;
}

int countComponents(int n, vector<vector<int>>& edges) {
    vector<int> parent(n); iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) -> int {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    };
    int count = n;
    for (auto& e : edges) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra != rb) {
            parent[ra] = rb;
            count--;
        }
    }
    return count;
}

public int countComponents(int n, int[][] edges) {
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int count = n;
    for (int[] e : edges) {
        int ra = find(parent, e[0]), rb = find(parent, e[1]);
        if (ra != rb) {
            parent[ra] = rb;
            count--;
        }
    }
    return count;
}
private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

def count_components(n, edges):
    parent = list(range(n))
    def find(x):
        if parent[x] != x: parent[x] = find(parent[x])
        return parent[x]
    count = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            count -= 1
    return count

function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  let count = n;
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) {
      parent[ra] = rb;
      count--;
    }
  }
  return count;
}

int countComponents(int n, vector<vector<int>>& edges) {
    vector<int> parent(n);
    vector<int> size(n, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    auto find = [&](int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    int count = n;
    for (int i = 0; i < (int)edges.size() && count > 1; i++) {
        int a = find(edges[i][0]), b = find(edges[i][1]);
        if (a == b) continue;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        count--;
    }
    return count;
}

public int countComponents(int n, int[][] edges) {
    int[] parent = new int[n];
    int[] size = new int[n];
    Arrays.fill(size, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    int count = n;
    for (int i = 0; i < edges.length && count > 1; i++) {
        int a = find(parent, edges[i][0]), b = find(parent, edges[i][1]);
        if (a == b) continue;
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        size[a] += size[b];
        count--;
    }
    return count;
}
private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

def count_components(n, edges):
    parent = list(range(n))
    size = [1] * n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    count = n
    for i in range(len(edges)):
        if count <= 1: break
        a, b = find(edges[i][0]), find(edges[i][1])
        if a == b: continue
        if size[a] < size[b]: a, b = b, a
        parent[b] = a
        size[a] += size[b]
        count -= 1
    return count

function countComponents(n: number, edges: number[][]): number {
  const parent = new Int32Array(n);
  const size = new Int32Array(n).fill(1);
  for (let i = 0; i < n; i++) parent[i] = i;
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };
  let count = n;
  for (let i = 0; i < edges.length && count > 1; i++) {
    let a = find(edges[i][0]), b = find(edges[i][1]);
    if (a === b) continue;
    if (size[a] < size[b]) [a, b] = [b, a];
    parent[b] = a;
    size[a] += size[b];
    count--;
  }
  return count;
}