Graph AlgosAlgorithmaka components of an undirected graph, flood fill labelling

Connected Components

Partition an undirected graph into maximal groups of mutually reachable vertices with one traversal per group.

▶ VisualizePattern: Breadth-First SearchPractice (4)
Progress

Overview

A connected component of an undirected graph is a maximal set of vertices in which every pair is joined by some path. Every vertex belongs to exactly one component, so the components partition the vertex set. A graph with a single component is called *connected*.

Finding components is the simplest use of graph traversal: start a Depth-First Search (DFS) or Breadth-First Search (BFS) from any unvisited vertex, label everything it reaches with the same id, then move on to the next unvisited vertex. Each traversal discovers exactly one component. The number of traversals started is the number of components.

For directed graphs the notion splits into weakly connected components (ignore edge direction) and Strongly Connected Components (respect direction, need Tarjan's SCC Algorithm or Kosaraju's Algorithm). This topic is about undirected graphs, or directed graphs treated as undirected.

undirectedreachabilityDFSBFSunion-findO(V + E)

Intuition

A mental model before the formal terms.

Picture the vertices as islands and the edges as bridges. Drop a bucket of paint on one island and let it flow across every bridge: everything that gets wet is one component. Then find a dry island and repeat with a new colour. The number of colours you used is the number of components — no colour ever leaks into another because there is, by definition, no bridge between them.

A 0/1 grid where 1 cells are land and adjacent land cells are joined ("Number of Islands") is exactly this problem; the adjacency list is implicit in the four grid directions.

How it works

  1. Build the adjacency list. For an undirected graph insert each edge (u, v) in both adj[u] and adj[v].
  2. Keep an array comp[v], initialised to -1 (unlabelled), and a counter count = 0.
  3. Scan vertices s = 0..n-1. If comp[s] is already set, skip it.
  4. Otherwise run a traversal from s (iterative DFS with an explicit stack or BFS with a queue). Whenever you first reach a vertex, set comp[vertex] = count and push it. Labelling on push (not pop) guarantees each vertex is pushed at most once.
  5. When the traversal drains, increment count. At the end count is the number of components and comp maps every vertex to its component id.
  6. Alternative: a Union-Find (Disjoint Set Union) structure. Union the endpoints of every edge; the number of components is n minus the number of successful unions. This is the natural choice when edges arrive online.

Why it works

A traversal from s visits exactly the vertices reachable from s. In an undirected graph reachability is symmetric and transitive, so "reachable from s" is precisely the component of s. No vertex outside the component can be reached (there is no edge into it), and no vertex inside can be missed (a path to it exists, and traversal follows every edge of every visited vertex).

Because every vertex is labelled once and every adjacency list is scanned once, the total work is O(V + E) regardless of how many components there are.

Recognition

How to tell a problem wants this.

  • The statement asks "how many groups / islands / provinces / clusters", or whether two vertices are "in the same network".
  • Relations that are symmetric (friendship, "adjacent land cells", "equations a == b") define an undirected graph, and the question is about groups under that relation.
  • You need a component id per vertex to answer many connectivity queries in O(1) afterwards.
  • Edges arrive one at a time and you must report the component count after each insert — use Union-Find (Disjoint Set Union) instead of re-running traversal.
“minimum steps” → Breadth-First Search“connected groups” → Depth-First Search“connected groups” → Union-Find

Interactive visualization

Play, step, change the input. ← → and space work too.

ABCDEFGHI
Stack
empty
1/15Scan nodes in order; each unlabeled node seeds a new component that a DFS floods. Two nodes share a label exactly when a path connects them.
Current nodeComponent 1, 4, …Component 2, 5, …Component 3, 6, …Traversal edge
PseudocodeLearn Connected Components →
1comp = {}; count = 0
2for s in nodes:
3  if s in comp: continue
4  count += 1; stack = [s]; comp[s] = count
5  while stack not empty:
6    u = stack.pop()
7    for v in neighbors(u):
8      if v not in comp: comp[v] = count; stack.push(v)
9return count
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1build adj (both directions)
2comp[0..n-1] = -1, count = 0
3for s in 0..n-1:
4  if comp[s] != -1: continue
5  comp[s] = count; stack = [s]
6  while stack not empty:
7    u = stack.pop()
8    for w in adj[u]:
9      if comp[w] == -1: comp[w] = count; stack.push(w)
10  count += 1
11return count, comp

Implementations

1def connected_components(n: int, edges: list[list[int]]) -> tuple[int, list[int]]:
2    """Return (number of components, comp) where comp[v] is the id of v's component."""
31 · Build undirected adjacency list
4    adj: list[list[int]] = [[] for _ in range(n)]
5    for u, v in edges:
6        adj[u].append(v)
7        adj[v].append(u)
8 
92 · Label array and counter
10    comp = [-1] * n
11    count = 0
12 
133 · Start one traversal per unlabelled vertex
14    for s in range(n):
15        if comp[s] != -1:
16            continue
17        comp[s] = count
18        stack = [s]
19 
204 · Iterative DFS, label on push
21        while stack:
22            u = stack.pop()
23            for w in adj[u]:
24                if comp[w] == -1:
25                    comp[w] = count
26                    stack.append(w)
27 
285 · One component finished
29        count += 1
30    return count, comp
Walkthrough
  1. [[] for _ in range(n)] builds independent lists; [[]] * n would alias one list.
  2. comp = [-1] * n is fine for immutable ints.
  3. A plain list is the idiomatic Python stack: append / pop() are amortised O(1).
  4. Neighbours are labelled before append, so no vertex is pushed twice.
  5. Returns a tuple (count, comp); callers unpack it.
Complexity (this implementation)
time O(V + E) · space O(V)
Language notes
  • Use list for a stack and collections.deque for a queue; list.pop(0) is O(n).
  • The iterative version avoids sys.setrecursionlimit; a recursive DFS dies at ~1000 frames by default.
  • Type hints list[list[int]] are Python 3.9+ builtin generics.
Common mistakes in this language
  • adj = [[]] * n creates one shared list.
  • Recursive DFS on a long path without raising the recursion limit — RecursionError.
  • Marking visited on pop, which lets a vertex be pushed once per incident edge.
Language differences that matter here
  • All four use an explicit stack; recursion would overflow in Python (~1000 frames) and JS/TS (~10k) on path-shaped graphs, while C++ typically survives ~10^5 frames.
  • C++ std::vector is the stack; JS/TS arrays with push/pop; Python list. None should be used as a FIFO queue (shift() / pop(0) are O(n)).
  • C++ returns a pair, JS/TS an object, Python a tuple.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Union-find variant: O(E α(V)) with path compression; effectively linear.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Counting groups / islands / clusters in a static undirected graph or grid.
  • Pre-computing a component id per vertex so that "are u and v connected?" is an O(1) array comparison.
  • As the first step of larger problems: e.g. solve something per component, or check that a graph is connected before running an MST or Eulerian algorithm.
Avoid it when
  • Directed graphs where direction matters — use Strongly Connected Components instead; treating edges as undirected gives only weak components.
  • Edges are added incrementally with queries in between — a traversal per query is O(V + E) each; Union-Find (Disjoint Set Union) answers in near-constant amortised time.
  • You need the components after deleting edges (offline: process deletions in reverse with union-find; online: much harder).

Alternatives

Union-Find (Disjoint Set Union)Breadth-First Search (BFS)Depth-First Search (DFS)Tarjan's SCC Algorithm
Compare: Union-Find vs DFS

Common mistakes

  • Marking a vertex visited on pop instead of on push in iterative DFS — a vertex can then be pushed many times and the stack blows up to O(E).
  • Forgetting to insert undirected edges in both directions; components then depend on which endpoint the traversal happened to start from.
  • Isolated vertices (no edges) are components too — never derive the count only from the edge list.
  • Recursive DFS on a 10^5-vertex path graph overflows the stack in Python/JavaScript; use the iterative version.

Interview patterns

  • Number of islands / number of provinces: flood fill on a grid or adjacency matrix.
  • Count components with union-find while streaming edges; the count is n - successfulUnions.
  • Check whether a graph is a tree: connected and exactly n - 1 edges.
  • Equations-satisfiable / accounts-merge style problems: group by symmetric relation, then process each group.
Interview questions on this
Mock interviews

Example problems

Number of IslandsmediumClone GraphmediumNumber of Connected ComponentsmediumRedundant Connectionmedium