Number of Connected Components in an Undirected Graph

Problem

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

Examples

The brute-force approach

Build an adjacency list and BFS/DFS from each unvisited node. Each new BFS/DFS that starts marks one connected component.

adj = defaultdict(list)
for a, b in edges:
    adj[a].append(b); adj[b].append(a)

visited = set()
components = 0
for node in range(n):
    if node not in visited:
        bfs(node, visited, adj)
        components += 1
return components

O(V + E) — actually optimal. Union-Find is often preferred for dynamic connectivity or when edges are added incrementally.

Spotting the pattern

This is a Union-Find problem. The key question to ask yourself:

Each node starts in its own "group." When you process edge [a, b], how do you check whether a and b are already in the same group?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.