Connected Components: DFS, BFS, and Union-Find Approaches

A connected component is a maximal set of vertices such that there is a path between every pair of vertices in the set. Finding connected components is one of the most fundamental graph operations. It answers the question: “which nodes can reach which other nodes?”

The number of connected components tells you how many isolated groups exist in your graph. Each group is fully connected internally but has no edges to other groups.

Approach 1: DFS (Depth-First Search)

The simplest approach. Start from an unvisited node, DFS to mark all reachable nodes as part of the same component. Repeat for the next unvisited node.

def count_components_dfs(n: int, edges: list[list[int]]) -> int:
    """
    Count connected components in an undirected graph.
    n: number of nodes (0 to n-1)
    edges: list of [u, v] edges
    """
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = set()
    components = 0
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
    
    for i in range(n):
        if i not in visited:
            dfs(i)
            components += 1
    
    return components

Collecting Components

If you need the actual groups, not just the count:

def find_components_dfs(n: int, edges: list[list[int]]) -> list[list[int]]:
    """Return list of components, each component is a list of nodes."""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = set()
    components = []
    
    def dfs(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, component)
    
    for i in range(n):
        if i not in visited:
            component = []
            dfs(i, component)
            components.append(component)
    
    return components

Iterative DFS (Stack-Safe)

For large graphs, use an explicit stack to avoid Python recursion limits:

def count_components_iterative_dfs(n: int, edges: list[list[int]]) -> int:
    """Iterative DFS to avoid stack overflow."""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = set()
    components = 0
    
    for i in range(n):
        if i in visited:
            continue
        components += 1
        stack = [i]
        while stack:
            node = stack.pop()
            if node in visited:
                continue
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return components

Approach 2: BFS (Breadth-First Search)

Same idea, but explore level by level. BFS is often preferred when you also need distances or when the graph is very wide.

from collections import deque

def count_components_bfs(n: int, edges: list[list[int]]) -> int:
    """BFS approach to counting connected components."""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = set()
    components = 0
    
    for i in range(n):
        if i in visited:
            continue
        components += 1
        queue = deque([i])
        visited.add(i)
        
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    
    return components

Approach 3: Union-Find

Union-Find (Disjoint Set Union) is particularly powerful for connected components because it handles dynamic graphs efficiently. As edges are added, components merge.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # number of components
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already connected
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)


def count_components_uf(n: int, edges: list[list[int]]) -> int:
    """Union-Find approach: process edges, count remaining components."""
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.count

Why Union-Find Shines

Union-Find excels when:

• Edges arrive dynamically: You can add edges one by one and always know the component count.
• You only have an edge list: No need to build an adjacency list first.
• You need to answer connectivity queries: “Are A and B in the same component?” is O(alpha(n)), essentially O(1).

Number of Islands (LeetCode 200)

The most famous connected components problem on grids. Given a 2D grid of ‘1’s (land) and ‘0’s (water), count the number of islands.

DFS Solution

def numIslands(grid: list[list[str]]) -> int:
    """Count islands using DFS flood fill."""
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '0'  # mark visited by sinking
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    
    return count

BFS Solution

from collections import deque

def numIslands_bfs(grid: list[list[str]]) -> int:
    """Count islands using BFS."""
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            count += 1
            queue = deque([(r, c)])
            grid[r][c] = '0'
            
            while queue:
                cr, cc = queue.popleft()
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))
    
    return count

Union-Find Solution

def numIslands_uf(grid: list[list[str]]) -> int:
    """Count islands using Union-Find."""
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    
    # Only create UF entries for land cells
    uf = UnionFind(rows * cols)
    water_count = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '0':
                water_count += 1
                continue
            # Union with right and down neighbors (avoid double-counting)
            idx = r * cols + c
            if r + 1 < rows and grid[r + 1][c] == '1':
                uf.union(idx, (r + 1) * cols + c)
            if c + 1 < cols and grid[r][c + 1] == '1':
                uf.union(idx, r * cols + c + 1)
    
    return uf.count - water_count

Largest Connected Component

Finding the size of the largest component is a common follow-up.

def largest_component(n: int, edges: list[list[int]]) -> int:
    """Find the size of the largest connected component."""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = set()
    max_size = 0
    
    def dfs(node):
        visited.add(node)
        size = 1
        for neighbor in graph[node]:
            if neighbor not in visited:
                size += dfs(neighbor)
        return size
    
    for i in range(n):
        if i not in visited:
            max_size = max(max_size, dfs(i))
    
    return max_size

Max Area of Island (LeetCode 695)

Find the largest island by area.

def maxAreaOfIsland(grid: list[list[int]]) -> int:
    """Find the largest island area using DFS."""
    rows, cols = len(grid), len(grid[0])
    max_area = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return 0
        if grid[r][c] != 1:
            return 0
        grid[r][c] = 0  # mark visited
        return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))
    
    return max_area

Number of Distinct Islands (LeetCode 694)

Two islands are distinct if one cannot be translated to match the other. Track the shape by recording relative positions.

def numDistinctIslands(grid: list[list[int]]) -> int:
    """Count distinct island shapes."""
    rows, cols = len(grid), len(grid[0])
    shapes = set()
    
    def dfs(r, c, origin_r, origin_c, shape):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != 1:
            return
        grid[r][c] = 0
        shape.append((r - origin_r, c - origin_c))
        dfs(r+1, c, origin_r, origin_c, shape)
        dfs(r-1, c, origin_r, origin_c, shape)
        dfs(r, c+1, origin_r, origin_c, shape)
        dfs(r, c-1, origin_r, origin_c, shape)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                shape = []
                dfs(r, c, r, c, shape)
                shapes.add(tuple(shape))
    
    return len(shapes)

Island Perimeter (LeetCode 463)

Not a connected components problem per se, but a common grid companion.

def islandPerimeter(grid: list[list[int]]) -> int:
    """Calculate island perimeter by counting exposed edges."""
    rows, cols = len(grid), len(grid[0])
    perimeter = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:
                continue
            # Each land cell contributes 4 sides
            # Subtract 1 for each adjacent land cell
            perimeter += 4
            if r > 0 and grid[r-1][c] == 1:
                perimeter -= 2  # shared edge counts for both cells
            if c > 0 and grid[r][c-1] == 1:
                perimeter -= 2
    
    return perimeter

Approach Comparison

Method	Time	Space	Best For
DFS	O(V + E)	O(V)	Simple graphs, recursion OK
BFS	O(V + E)	O(V)	When you need distances too
Union-Find	O(E * alpha(V))	O(V)	Dynamic edges, edge lists

For grids with R rows and C columns:

• V = R * C (each cell is a vertex)
• E = up to 4 * R * C (4-directional neighbors)
• Total: O(R * C) for all approaches

When to Pick Which

• DFS: Default choice. Simple, fast, easy to modify for collecting components or tracking properties (like island area or shape).
• BFS: When you also need shortest distances, or when the graph is very deep (DFS might hit recursion limits).
• Union-Find: When edges arrive over time, when you need to answer “are X and Y connected?” queries efficiently, or when you only have an edge list.

Accounts Merge (LeetCode 721)

A more complex connected components problem. Emails belonging to the same person form a component.

def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:
    """Merge accounts that share emails using Union-Find."""
    from collections import defaultdict
    
    email_to_id = {}
    email_to_name = {}
    uf = UnionFind(10001)
    idx = 0
    
    for account in accounts:
        name = account[0]
        for email in account[1:]:
            if email not in email_to_id:
                email_to_id[email] = idx
                idx += 1
            email_to_name[email] = name
            # Union all emails in same account
            uf.union(email_to_id[account[1]], email_to_id[email])
    
    # Group emails by root
    groups = defaultdict(list)
    for email, eid in email_to_id.items():
        root = uf.find(eid)
        groups[root].append(email)
    
    # Format result
    result = []
    for root, emails in groups.items():
        emails.sort()
        name = email_to_name[emails[0]]
        result.append([name] + emails)
    
    return result

Complexity Analysis Deep Dive

DFS/BFS: Both are O(V + E). Every vertex is visited once and every edge is examined once (from each endpoint). Space is O(V) for the visited set, plus O(V) for the recursion stack (DFS) or queue (BFS) in the worst case.

Union-Find with path compression and union by rank:

• Each find and union is O(alpha(V)) amortized, where alpha is the inverse Ackermann function.
• alpha(V) < 5 for any practical V (up to 2^65536).
• Total for E edges: O(E * alpha(V)), which is effectively O(E).

Practice Problems

Problem	Difficulty	Key Concept
LeetCode 200: Number of Islands	Medium	Grid DFS/BFS
LeetCode 323: Number of Connected Components	Medium	Standard components
LeetCode 695: Max Area of Island	Medium	Component size
LeetCode 721: Accounts Merge	Medium	Union-Find grouping
LeetCode 694: Number of Distinct Islands	Medium	Shape tracking
LeetCode 463: Island Perimeter	Easy	Grid counting
LeetCode 547: Number of Provinces	Medium	Adjacency matrix components

Key Takeaways

1. Connected components = number of DFS/BFS calls needed to visit every node.
2. Grid problems are graph problems where each cell is a node with 4 (or 8) neighbors.
3. Union-Find is best for dynamic connectivity where edges are added over time.
4. Mark visited before enqueueing in BFS to avoid duplicate processing.
5. In-place marking (changing grid values) saves space but modifies the input. Clone the grid if you need to preserve it.