MediumBlind75GraphDFSBFSUnion Find

Number of Connected Components in an Undirected Graph

Given n nodes and an undirected edges list, find the number of connected components.

Examples

Input
n = 5, edges = [[0,1],[1,2],[3,4]]
Output
2

Components: {0,1,2} and {3,4}.

Input
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output
1

All nodes are connected.

Constraints

  • •1 <= n <= 2000
  • •0 <= edges.length <= 5000
  • •edges[i].length == 2
  • •0 <= ai, bi < n
  • •ai != bi
  • •There are no repeated edges.

Approaches

Use DFS to count connected components.

CodeT: O(V + E) | S: O(V + E)
def count_components(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = [False] * n
    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
    count = 0
    for i in range(n):
        if not visited[i]:
            count += 1
            dfs(i)
    return count

Use BFS to count connected components.

CodeT: O(V + E) | S: O(V + E)
from collections import deque

def count_components(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = [False] * n
    count = 0
    for i in range(n):
        if not visited[i]:
            count += 1
            queue = deque([i])
            visited[i] = True
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
    return count

Use Union Find to count connected components.

Diagram

n=5, edges=[[0,1],[1,2],[3,4]] Union: (0,1), (1,2), (3,4) Find roots: {0,1,2} -> root 0, {3,4} -> root 3 Components = 2
CodeT: O(n * alpha(n)) | S: O(n)
def count_components(n, edges):
    parent = list(range(n))
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
    for u, v in edges:
        union(u, v)
    return len(set(find(i) for i in range(n)))

Complexity Comparison

DFS - Visit All Nodes
T: O(V + E)S: O(V + E)

Use DFS to count connected components.

BFS
T: O(V + E)S: O(V + E)

Use BFS to count connected components.

Union Find
T: O(n * alpha(n))S: O(n)

Use Union Find to count connected components.

Common Mistakes

Not counting isolated nodes as components

Using Union Find without path compression

Forgetting to handle nodes with no edges

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems