Connected Components

A connected component of an undirected graph is a maximal subset of vertices such that every pair within the subset is joined by some path. Every undirected graph is uniquely partitioned into connected components — the equivalence classes of the relation “u and v are connected.” Three standard algorithms compute components in O(V + E) time: BFS, DFS, and Union-Find (a.k.a. Disjoint Set Union, DSU). The choice between them is a trade-off: BFS/DFS are natural for static graphs (you have all edges up front and want to label components in one pass); Union-Find is natural for incremental / online graphs (edges arrive one at a time and you need ongoing connectivity queries). For directed graphs, “connected” splits into the strictly-stronger strongly connected and the weakly-equivalent (treat as undirected) variants — see Strongly Connected Components.

1. Intuition — Friend Groups in a Social Network

Consider a social network where friendships are mutual (undirected edges). A connected component is a friend cluster: every two people in it are reachable through some chain of friends, but nobody in the cluster is connected to anyone outside.

If you want to count “how many friend groups exist?”, three tactics:

• BFS: start at someone you haven’t seen; BFS-explore the whole cluster, marking everyone visited; that’s one component. Find the next unseen person; repeat.
• DFS: identical to BFS conceptually; the only difference is the traversal order within a component (depth-first vs breadth-first). Same O(V + E).
• Union-Find: for each friendship edge (u, v), merge their groups (union(u, v)). At the end, the number of distinct groups (= number of distinct roots) is the answer.

All three reach the same answer with the same asymptotic cost. The interesting question is when each is preferred, which depends on whether edges are static or arrive online, whether you need component IDs or just a count, and whether the graph fits in memory.

For directed graphs, “connectivity” is ambiguous: do you mean “u can reach v”? “u can reach v and v can reach u”? The first (“weakly connected”) is computed by treating the graph as undirected. The second (“strongly connected”) is much harder and requires Tarjan’s or Kosaraju’s algorithm — see Strongly Connected Components. This note is about the undirected case.

2. Tiny Worked Example

Vertices 0..7, undirected edges {(0,1), (1,2), (3,4), (5,6), (6,7), (5,7)}. Vertex 8 has no edges (an isolated vertex).

0 — 1 — 2          3 — 4          5 — 6
                                  |   |
                                  7 — ┘

8     (isolated)

By inspection: 4 components.

• Component 1: {0, 1, 2}
• Component 2: {3, 4}
• Component 3: {5, 6, 7}
• Component 4: {8}

Each algorithm in §3–§5 will produce these same four sets.

3. BFS Approach

3.1 Pseudocode

count_components_bfs(graph, n):
    visited := array, all false
    component_id := array, all -1
    count := 0
    for each s in 0..n-1:
        if not visited[s]:
            count += 1
            queue := [s]
            visited[s] := true
            while queue not empty:
                u := dequeue
                component_id[u] := count - 1         # 0-indexed
                for each v in graph[u]:
                    if not visited[v]:
                        visited[v] := true
                        enqueue v
    return count, component_id

3.2 Python Implementation

from collections import deque
 
def connected_components_bfs(graph: dict[int, list[int]], n: int) -> tuple[int, list[int]]:
    """
    graph: undirected adjacency list, vertex -> list of neighbors.
    n: number of vertices, 0..n-1.
    Returns: (component_count, component_id[v] = which component v belongs to).
    """
    component_id = [-1] * n
    count = 0
    for s in range(n):
        if component_id[s] != -1:
            continue
        # New component
        component_id[s] = count
        q = deque([s])
        while q:
            u = q.popleft()
            for v in graph.get(u, []):
                if component_id[v] == -1:
                    component_id[v] = count
                    q.append(v)
        count += 1
    return count, component_id

The component_id array doubles as the visited marker: -1 means unvisited.

3.3 Trace

Start s=0: BFS labels 0, 1, 2 with component 0. Next unvisited s=3: BFS labels 3, 4 with component 1. Next s=5: BFS labels 5, 6, 7 with component 2. Next s=8: BFS labels 8 with component 3. Total = 4. Matches §2.

4. DFS Approach

4.1 Pseudocode (Recursive)

count_components_dfs(graph, n):
    component_id := array, all -1
    count := 0
    for each s in 0..n-1:
        if component_id[s] == -1:
            dfs(s, count)
            count += 1
    return count, component_id

dfs(u, label):
    component_id[u] := label
    for each v in graph[u]:
        if component_id[v] == -1:
            dfs(v, label)

4.2 Python Implementation (Iterative — Avoids Recursion Limit)

def connected_components_dfs(graph: dict[int, list[int]], n: int) -> tuple[int, list[int]]:
    component_id = [-1] * n
    count = 0
    for s in range(n):
        if component_id[s] != -1:
            continue
        stack = [s]
        component_id[s] = count
        while stack:
            u = stack.pop()
            for v in graph.get(u, []):
                if component_id[v] == -1:
                    component_id[v] = count
                    stack.append(v)
        count += 1
    return count, component_id

The recursive form is shorter but blows up on long-chain graphs (10^5 vertices in a path overflows Python’s recursion limit of 1000). The iterative form scales.

4.3 BFS vs DFS for Components — Why Both Work the Same Asymptotically

The only thing that matters for component identification is “visit every vertex reachable from s.” Both BFS and DFS do exactly that, both in O(V_s + E_s) per component (where V_s, E_s are the size of the component containing s). Summed over all components, both are O(V + E) total.

The visit order differs (layer-by-layer for BFS, branch-by-branch for DFS), but for component labeling that’s irrelevant — every vertex in the component eventually gets the same label either way.

When does the choice matter? When you need more than just the label:

• Need shortest-path distance from a source to every other vertex within its component? BFS (gives unweighted shortest paths).
• Need to detect cycles, find articulation points, or do post-order processing within the component? DFS (the classical framework — see Bridges and Articulation Points).
• Need to handle deep graphs where recursion depth is an issue? BFS (no recursion stack) or iterative DFS.
• Need to process largest-component-first? Run the labeling first, then sort components by size — algorithm choice doesn’t matter for that.

5. Union-Find Approach

5.1 Idea

Treat each vertex as initially in its own singleton component. For each edge (u, v), call union(u, v). After processing all edges, the number of distinct components is the number of distinct roots; alternatively, maintain a counter that decrements every time union actually merges two distinct sets.

5.2 Python Implementation

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n                          # number of components
 
    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]    # path-halving
            x = self.parent[x]
        return x
 
    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        self.count -= 1
        return True
 
def connected_components_uf(edges: list[tuple[int, int]], n: int) -> int:
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.count

See the Union-Find note for a full treatment of path compression, union by rank/size, and the inverse-Ackermann analysis.

5.3 When Union-Find Wins

The defining feature: Union-Find supports incremental edge addition with O(α(n)) amortized per operation, where α is the inverse Ackermann function (effectively constant for practical n).

Imagine edges arrive one at a time and after each edge you need to answer “is the graph connected?” or “how many components remain?” or “are u and v now connected?”. With BFS/DFS, you’d re-run the whole O(V+E) algorithm after each edge — total cost O(E·(V+E)). With Union-Find, each edge is processed in O(α(n)) amortized — total cost O((V+E)·α(n)), which is essentially O(V+E). Massive win.

By contrast, for a static graph where you have all edges up front, BFS/DFS and Union-Find are both O(V+E) and equally good — choose whichever is more natural for the surrounding code.

Edge removal is fundamentally harder

Standard Union-Find supports union (edge insertion) but not edge deletion. If your problem requires deleting edges and re-querying connectivity, you need link-cut trees or Euler tour trees, with O(log² n) per operation (Holm-Lichtenberg-Thorup, 2001). Or — if deletions are rare — recompute components from scratch with BFS/DFS.

6. Comparing the Three Approaches

Property	BFS	DFS	Union-Find
Time (static graph)	O(V + E)	O(V + E)	O((V + E)·α(n)) ≈ O(V + E)
Time (online, edges arrive one-by-one)	O(E·(V+E)) (recompute each time)	same	O((V + E)·α(n)) ✓
Space	O(V) (queue + visited)	O(V) (stack + visited)	O(n) (parent + size)
Returns shortest paths within component?	✓ (unweighted)	✗	✗
Returns component IDs?	✓	✓	via find(v) (need to canonicalize)
Returns largest-component size?	✓ (count during traversal)	✓	✓ (read size[root])
Supports edge deletion?	✗ (recompute)	✗	✗ (need link-cut trees)
Supports connectivity queries online?	✗ (recompute)	✗	✓ in O(α(n))
Recursion stack risk?	None	Yes (recursive) / None (iterative)	None
Easy to parallelize?	Marginally	Hard	Marginally

Decision guide:

• Static graph, just need component count or labels: BFS or DFS — pick whichever is more idiomatic in your code.
• Static graph, need shortest paths within components too: BFS (cheaper than running BFS later separately).
• Online edges, need ongoing connectivity queries: Union-Find. Always.
• Online edges with deletions: Out of scope for these three; need link-cut or Euler tour trees.
• Need to find articulation points / bridges / SCCs as side effects: DFS (those algorithms are DFS-based).

7. The Mathematical Definition

The relation R(u, v) ≡ "there is a path from u to v" on the vertex set of an undirected graph is an equivalence relation:

• Reflexive: R(u, u) — the trivial path of length 0.
• Symmetric: R(u, v) ⟹ R(v, u) — paths in undirected graphs are reversible.
• Transitive: R(u, v) and R(v, w) ⟹ R(u, w) — concatenate the paths.

Equivalence classes of R are exactly the connected components. This is the formal definition — the algorithms in §3–§5 all compute exactly this partition.

For directed graphs, the analogous relation R(u, v) ≡ "u can reach v and v can reach u" is also an equivalence relation, and its classes are the strongly connected components (Strongly Connected Components). The relation R'(u, v) ≡ "u can reach v" alone is not symmetric and hence not an equivalence relation — that’s the asymmetry that makes directed connectivity harder.

8. Variants and Extensions

8.1 Counting Vertices in Each Component

While doing BFS/DFS, count the number of vertices visited in each component traversal. Or with Union-Find, read size[find(v)] for any representative.

8.2 Largest Connected Component

After computing component sizes (via §8.1), max(sizes). O(V + E) total.

8.3 Number of Edges Within Each Component

For each edge (u, v), increment edge_count[component_id[u]]. With BFS/DFS labeling done first, this is one pass through edges. With Union-Find, identify the component representative for each edge endpoint and increment.

8.4 Connected-Components in Grids

Many interview problems pose components on a 2D grid: cells are vertices, neighbors are 4-connected (or 8-connected). The algorithms are unchanged — just generate adjacency on-the-fly. This is the classic “Number of Islands” pattern (LC 200).

8.5 Online Component Maintenance with Predicate-Based Merge

Some problems define edges implicitly (e.g., “merge two cells if they have the same color”). Iterate over candidate edges and call union. Same O((V+E)·α(n)).

8.6 Component Identification Across Filtering

Given a base graph and a filter (e.g., “consider only edges with weight ≤ k”), Union-Find with sorted edges incrementally builds the components as k grows. This is the heart of Kruskal’s MST and the offline minimum-spanning-tree query algorithm.

8.7 Weakly Connected Components in Directed Graphs

Treat the directed graph as undirected (replace each directed edge with an undirected one) and run BFS/DFS/Union-Find. The resulting components are the weakly connected components. Different from — and always coarser than — strongly connected components.

9. Use Cases and Why Components Matter

9.1 Cluster Analysis in Social and Biological Networks

Identifying friend clusters, gene-interaction modules, web-community detection. Often the number of clusters and the size distribution are the headline statistics.

9.2 Image Segmentation (Connected-Component Labeling)

In computer vision, after binarizing an image, each foreground “blob” is a connected component of pixels (4- or 8-connected). The classical Hopcroft-Tarjan two-pass labeling algorithm uses Union-Find to merge components that turn out to be the same after the second pass.

9.3 Reachability Queries in Static Graphs

“Are servers A and B in the same network partition?” Precompute components once in O(V+E), then answer queries in O(1) (compare component IDs).

9.4 Network Reliability

If a network’s underlying graph has more than one component, parts of the network are unreachable from each other. Component count directly measures partitioning. (Compare with Bridges and Articulation Points, which identifies which edges/vertices, if removed, would create new components.)

9.5 Preprocessing for Other Algorithms

Many graph algorithms assume a connected graph. Component labeling first, then run the algorithm on each component independently, is a standard preprocessing step.

9.6 Percolation and Critical Phenomena

In statistical physics, the question “at what edge-density does a giant component emerge?” is the percolation threshold. Erdős-Rényi random-graph theory shows it occurs at p = 1/n for sparse graphs — and Union-Find efficiently simulates this.

9.7 Spam-Account Clustering

Identify groups of accounts that share IP addresses, devices, or other identifiers — model as graph with shared-identifier edges and compute components.

10. Common Interview Problems

Problem	Pattern
LC 200 — Number of Islands	Grid 4-connected DFS/BFS
LC 547 — Number of Provinces	Adjacency-matrix DFS or Union-Find
LC 323 — Number of Connected Components in an Undirected Graph	Direct application of any of three approaches
LC 305 — Number of Islands II	Online: edges added one at a time → Union-Find shines
LC 695 — Max Area of Island	DFS, return area via post-order
LC 130 — Surrounded Regions	DFS from boundary inward
LC 1319 — Number of Operations to Make Network Connected	Components + (extra-edge availability)
LC 1971 — Find if Path Exists in Graph	Union-Find or BFS/DFS
Codeforces — “Online edge addition with connectivity queries”	Union-Find

If a problem mentions “how many groups”, “are X and Y connected”, “merge clusters”, or “add edges and ask connectivity” — connected-components is the natural model.

11. Diagram — Three Approaches on the Same Graph

flowchart LR
  subgraph "BFS labeling from s=0"
    A0((0)) --- A1((1)) --- A2((2))
    style A0 fill:#fdd
    style A1 fill:#fdd
    style A2 fill:#fdd
  end
  subgraph "DFS labeling from s=3"
    B3((3)) --- B4((4))
    style B3 fill:#dfd
    style B4 fill:#dfd
  end
  subgraph "Union-Find merging on (5,6) then (5,7)"
    C5((5)) --- C6((6))
    C5 --- C7((7))
    style C5 fill:#ddf
    style C6 fill:#ddf
    style C7 fill:#ddf
  end

What this diagram shows. Three subgraphs corresponding to the three components of the §2 example, each colored to indicate it’s been processed by one approach. In practice you’d use one approach for the whole graph; the diagram juxtaposes them to emphasize that BFS, DFS, and Union-Find all converge on the same partition. The colors highlight that the output — three components — is identical; only the bookkeeping differs. The choice between the three approaches is made on grounds of online vs offline, recursion safety, what extra info you need (shortest paths? articulation points?), not correctness.

12. Pitfalls

12.1 Forgetting the Outer Loop

Naive code does BFS/DFS only from vertex 0 and counts that as the answer. This misses every other component. Always iterate for s in range(n) and start a new traversal from each unvisited vertex.

12.2 Confusing Vertex Count With Component Count

The number of components is not the number of vertices, nor the number of “starts” of BFS/DFS minus something. It’s exactly the number of times the outer loop launched a traversal — i.e., the number of “fresh starts.” Increment your counter inside the if not visited branch.

12.3 Treating Directed Graphs as Undirected by Accident

If your input is a directed graph (e.g., asymmetric adjacency list), and you naively run undirected-style BFS, you’ll compute the weakly connected components — not the strongly connected ones. If the problem says “strongly connected,” you need Tarjan or Kosaraju instead.

12.4 Recursion Depth in DFS

Iterative DFS or sys.setrecursionlimit(N) for deep graphs. The recursive form is shorter but fails on adversarial inputs. The first thing you do in any DFS-based interview answer should be: “I’ll use iterative DFS [or set the recursion limit] to avoid stack overflow.”

12.5 Counting Components Wrongly with Union-Find

If you naively iterate for u in range(n): roots.add(find(u)), the path-compression side effects are correct, but you must call find(u), not read parent[u] directly (which may give an intermediate parent, not the canonical root). The cleanest approach is to maintain count inside the Union-Find class as in §5.2.

12.6 Using BFS/DFS for Online Edge-Insertion Queries

The asymptotically wrong choice. Re-running BFS after each edge insertion is O(E·(V+E)) total — quadratic in E. Union-Find achieves O((V+E)·α(n)). On 10^5 edges, the difference is hours vs milliseconds.

12.7 Modifying Graph During Traversal

Mutating graph[u] during BFS/DFS over graph[u] is undefined in Python (RuntimeError: dictionary changed size). Iterate over a copy if you must mutate.

12.8 Assuming Graph is Connected

A graph with a single isolated vertex has 2 components, not 1. Always include isolated vertices in your enumeration: the outer loop iterates 0..n-1, not just over keys of the adjacency list.

12.9 Off-by-One in Vertex Numbering

If your graph is 1-indexed but you allocate arrays of size n (0-indexed), you’ll get either IndexError or silent wrong answers. Normalize at input boundary or allocate arrays of size n + 1.

12.10 Choosing the Wrong Algorithm for the Side-Effects You Need

You need both component IDs and shortest paths within components → run BFS, not DFS. You need both component IDs and articulation points → run DFS with the AP algorithm bolted on (see Bridges and Articulation Points). You’re being scored on knowing the right tool, not on memorizing all three implementations.

13. Open Questions

• What’s the optimal data structure for fully dynamic connectivity (insertions + deletions) with worst-case bounds (not amortized)? Open in the deepest sense — recent work has narrowed but not closed the gap.
• How does connected-component algorithm choice change for external memory (graphs that don’t fit in RAM)? Specialized I/O-efficient algorithms exist (Munagala-Ranade); not standard interview material.

14. See Also

• Breadth-First Search — one of the three classical algorithms
• Depth-First Search — another, plus the foundation for related problems
• Union-Find — the natural choice for online connectivity queries
• Strongly Connected Components — the directed-graph analog (much more involved)
• Bridges and Articulation Points — identifies edges/vertices whose removal increases component count
• Kruskal’s Algorithm — uses Union-Find on sorted edges, produces MST + implicit component history
• Bipartite Check — a property checked per-component
• Graph Representations — how the graph is stored affects which algorithm is most natural
• Big-O Notation
• SWE Interview Preparation MOC