Connected Components: Counting Islands in a Graph

A connected component is a maximal group of vertices in an undirected graph that can all reach one another. If you drop a graph on the floor and it splits into separate clusters, each cluster is one component. Counting components answers questions like “how many separate friend groups are there?” or “how many islands?” You find them by running BFS or DFS from every not-yet-visited vertex.

The core idea

Loop over all vertices. Each time you hit one that hasn’t been visited, you’ve found a new component — start a traversal from it, which marks every vertex reachable from it as visited, then increment your counter. The outer loop guarantees you catch every disconnected piece.

int countComponents(const std::vector<std::vector<int>>& adj) {
    int n = adj.size(), count = 0;
    std::vector<bool> visited(n, false);
    for (int s = 0; s < n; s++) {
        if (visited[s]) continue;
        count++;
        std::queue<int> q;            // BFS flood fill
        q.push(s); visited[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u])
                if (!visited[v]) { visited[v] = true; q.push(v); }
        }
    }
    return count;
}

int countComponents(List<List<Integer>> adj) {
    int n = adj.size(), count = 0;
    boolean[] visited = new boolean[n];
    for (int s = 0; s < n; s++) {
        if (visited[s]) continue;
        count++;
        Queue<Integer> q = new ArrayDeque<>();   // BFS flood fill
        q.add(s); visited[s] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u))
                if (!visited[v]) { visited[v] = true; q.add(v); }
        }
    }
    return count;
}

function countComponents(adj) {
  const n = adj.length;
  const visited = new Array(n).fill(false);
  let count = 0;
  for (let s = 0; s < n; s++) {
    if (visited[s]) continue;
    count++;
    const queue = [s];                 // BFS flood fill
    visited[s] = true;
    let head = 0;
    while (head < queue.length) {
      const u = queue[head++];
      for (const v of adj[u])
        if (!visited[v]) { visited[v] = true; queue.push(v); }
    }
  }
  return count;
}

from collections import deque

def count_components(adj):
    n = len(adj)
    visited = [False] * n
    count = 0
    for s in range(n):
        if visited[s]:
            continue
        count += 1
        q = deque([s])                 # BFS flood fill
        visited[s] = True
        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    q.append(v)
    return count

Tip: You could swap the BFS flood fill for a recursive DFS — the component count is identical. Use whichever you find clearer; DFS is shorter to write, BFS avoids deep recursion.

Labeling each component

Often you want more than a count — you want to know which component each vertex belongs to. Replace the boolean visited with an integer comp array, writing the current component id as you traverse.

std::vector<int> labelComponents(const std::vector<std::vector<int>>& adj) {
    int n = adj.size(), id = 0;
    std::vector<int> comp(n, -1);
    for (int s = 0; s < n; s++) {
        if (comp[s] != -1) continue;
        std::queue<int> q; q.push(s); comp[s] = id;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u])
                if (comp[v] == -1) { comp[v] = id; q.push(v); }
        }
        id++;
    }
    return comp;
}

int[] labelComponents(List<List<Integer>> adj) {
    int n = adj.size(), id = 0;
    int[] comp = new int[n];
    Arrays.fill(comp, -1);
    for (int s = 0; s < n; s++) {
        if (comp[s] != -1) continue;
        Queue<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u))
                if (comp[v] == -1) { comp[v] = id; q.add(v); }
        }
        id++;
    }
    return comp;
}

function labelComponents(adj) {
  const n = adj.length;
  const comp = new Array(n).fill(-1);
  let id = 0;
  for (let s = 0; s < n; s++) {
    if (comp[s] !== -1) continue;
    const queue = [s]; comp[s] = id;
    let head = 0;
    while (head < queue.length) {
      const u = queue[head++];
      for (const v of adj[u])
        if (comp[v] === -1) { comp[v] = id; queue.push(v); }
    }
    id++;
  }
  return comp;
}

from collections import deque

def label_components(adj):
    n = len(adj)
    comp = [-1] * n
    cid = 0
    for s in range(n):
        if comp[s] != -1:
            continue
        q = deque([s]); comp[s] = cid
        while q:
            u = q.popleft()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = cid
                    q.append(v)
        cid += 1
    return comp

Complexity and notes

Time: O(V + E) — every vertex starts at most one traversal, and each edge is seen once.
Space: O(V).

Connected components apply to undirected graphs. The directed analogue — strongly connected components, where every vertex must reach every other along directed edges — needs algorithms like Tarjan’s or Kosaraju’s, beyond this page. A closely related technique for components under incremental unions is union-find.

Next: detect loops with cycle detection.