323. Number of Connected Components in an Undirected Graph

Summary

Return the number of connected components in the graph.

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Approach

Use DFS and keep track of visited nodes.

Function

Initialization:

visited: set of the node numbers.
graph: hashmap. The key is the node number, and the value is the list of connected nodes.
ans: integer, 0.

Function traverse:

argument: i, the node number.

If i is visited, return. Add i to visited. For each edge in graph[i]: traverse(edge)

For each node i: If i is already visited, continue. Call traverse(i). ans += 1

Return ans.

Complexity

Time Complexity: O(V+E). Space Complexity: O(V+E). The visited set requires O(V), the graph requires O(V+E), and the recursion stack for traverse is O(V) in the worst case, such as when all nodes are connected in a single line.

Quiz

What if you cannot build the graph?

Approach

We do not need to explicitly construct the adjacency list (graph).

Instead, we track which nodes belong to the same connected component using Union-Find (Disjoint Set Union).

Initially, each node is its own component. For each edge [u, v], we merge the components of u and v. If they are already connected, we do nothing. Each successful union reduces the number of connected components by 1.

Function

parent = array of size n size = array of size n

for i in 0..n-1: parent[i] = i size[i] = 1

components = n

Function find(x): if parent[x] != x: parent[x] = find(parent[x]) # path compression return parent[x]

Function union(x, y): rootX = find(x) rootY = find(y)

if rootX == rootY:
    return 0   # already in same component

# union by size
if size[rootX] < size[rootY]:
    parent[rootX] = rootY
    size[rootY] += size[rootX]
else:
    parent[rootY] = rootX
    size[rootX] += size[rootY]

return 1

for (u, v) in edges: components -= union(u, v)

return components

Complexity

Time Complexity: O(Eα(V))

Each edge performs find and union. With path compression + union by size, each operation is amortized O(α(V)). α(V) (the inverse Ackermann function) grows extremely slowly and is effectively constant in practice.

Space Complexity: O(V).