Connected Components

Connected Components

A connected component is a maximal set of nodes where every pair has a path between them. A connected graph has exactly one component.

Graph: 0 — 1     2 — 3     4

Components: {0,1}, {2,3}, {4}
count = 3

Algorithm

Iterate over all nodes. For each unvisited node, start a BFS/DFS — this discovers one complete component. Count how many times you start a new traversal.

def count_components(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    seen = set()
    count = 0

    def visit(node):
        seen.add(node)
        for nb in graph[node]:
            if nb not in seen:
                visit(nb)

    for node in range(n):
        if node not in seen:
            count += 1
            visit(node)

    return count

Applications

• Network connectivity analysis
• Image segmentation (connected pixels)
• Finding islands in a grid
• Social network clustering

Your Task

Implement count_components(n, edges) that returns the number of connected components in an undirected graph with n nodes.