Connected Components

Problem Statement

Count the number of connected components in an undirected graph.

Example: Graph with edges [[0,1],[1,2],[3,4]] → 2 connected components: {0,1,2} and {3,4}

Approach 1: DFS

Explanation: Traverse unvisited nodes recursively; each traversal counts as a component.

Time Complexity: O(V + E)

Space Complexity: O(V) recursion stack

visited = set()
count = 0
for node in all_nodes:
    if node not visited:
        DFS(node)
        count += 1

Approach 2: BFS

Explanation: Traverse using queue for unvisited nodes to find connected components.

Time Complexity: O(V + E)

Space Complexity: O(V)

visited = set()
count = 0
for node in all_nodes:
    if node not visited:
        queue = [node]
        visited.add(node)
        while queue not empty:
            curr = queue.pop()
            for neighbor in curr.neighbors:
                if neighbor not visited:
                    queue.push(neighbor)
                    visited.add(neighbor)
        count += 1

Approach 3: Union-Find

Explanation: Merge connected nodes; the number of disjoint sets = number of components.

Time Complexity: O(E α(V))

Space Complexity: O(V)

parent = [i for i in range(V)]
function find(x):
    if parent[x] != x: parent[x] = find(parent[x])
    return parent[x]
function union(x, y):
    parent[find(x)] = find(y)
for each edge (u,v):
    union(u,v)
count = number of unique parents