Number of Connected Components in an Undirected Graph

Explanation & Solution

Description

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.

Return the number of connected components in the graph.

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

Output: 2

Explanation: There are two connected components: {0, 1, 2} and {3, 4}.

Constraints

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

Approach

Union Find pattern

1. Initialize Union Find

Create a parent array where each node i is its own parent
Create a rank array initialized to 0 for union by rank
Set components = n since initially every node is its own component

2. Implement Find with Path Compression

The find function traces up the parent chain to find the root
Path compression: set each node's parent directly to the root during recursion
This ensures near-constant time for future lookups

3. Implement Union by Rank

Find the roots of both nodes
If they share the same root, they are already in the same component — do nothing
Otherwise, merge the smaller-rank tree under the larger-rank tree
Decrement `components` each time a successful union occurs (two components merge into one)

4. Process All Edges

For each edge [u, v], call union(u, v)
Each successful union reduces the component count by 1
Edges connecting already-connected nodes have no effect

5. Return Component Count

After processing all edges, components holds the number of connected components
Started at n and decreased by 1 for each merge

Key Insight

Start with n isolated nodes (n components) and merge as edges are added
Each edge either merges two components (decrement count) or connects already-connected nodes (no change)
Union Find with path compression and union by rank gives nearly O(α(n)) per operation

Time

**O(E · α(n))** where E is the number of edges

Space

O(n) for parent and rank arrays

Visualization

Input:

Connected Components5 nodes, 3 edges

output—

Press play to start connected components

CurrentQueuedVisited

9 steps

Solution Code

Number of Provinces

Graph Valid Tree