Difficulty: MediumGraphs

Number of Connected Components in an Undirected Graph

Problem in Plain English

Given a node count and undirected edges, count how many separate connected groups exist. Isolated nodes each count as their own group.

Problem Statement

You are given n nodes labeled 0 to n - 1 and undirected edges with edges[i] = [a, b].

Return the number of connected components: maximal groups of mutually reachable nodes. A node with no edges forms a component of its own.

Constraints

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= a, b < n
No repeated edges.

Examples

Example 1

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

Nodes 0, 1 and 2 link together while nodes 3 and 4 form a second group.

Example 2

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

The chain links every node, so the whole graph is a single component.

Example 3

Input: n = 4, edges = []
Output: 4

All four nodes are isolated, so each is its own connected component. Looking only at endpoints would miss every one.

Example 4

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

The triangle contains one group, not three merges: its last edge closes a cycle. Nodes 3 and 4 make the other group, so the answer is 2.

Intuition

A connected component contains all nodes reachable from one another. In Example 1, edges 0-1 and 1-2 join three nodes, while 3-4 joins a separate pair. Begin with five individual groups and let edges connect them: there are three genuine merges, leaving two groups. A cycle does not create a new merge once its endpoints are already connected, and a node absent from every edge must still be counted.

Approaches

Label Propagation

Solution Details

Reveal Label Propagation: intuition, complexity, and code

Intuition

Give every node its own label, then repeatedly let each edge pull its endpoints toward the smaller label until nothing changes. The surviving labels equal the components, but every sweep re-reads all edges even when almost nothing moves.

Step-by-Step Logic

Initialize label[i] = i for every node, including isolated nodes; Example 1 starts [0,1,2,3,4].
In each sweep process edges in input order. Compute the smaller current endpoint label before updating either endpoint, and copy it to both. Edge [0,1] makes [0,0,2,3,4]; [1,2] then makes [0,0,0,3,4].
Set changed whenever a label falls. Edge [3,4] produces [0,0,0,3,3], so repeat the sweep. Labels may need multiple sweeps when edges appear in reverse path order.
Stop only after a complete unchanged sweep, then count unique labels. Example 1 stabilizes in sweep 2 with {0,3}, giving 2.

Why It Works

Initially each label is a node in its own component. Copying a smaller label across an edge never moves a label between different components, and labels decrease monotonically. For a component whose smallest node is s, label s stays s forever. After each complete sweep, that label has reached at least one more edge along every path from s, so at most n - 1 changing sweeps suffice. Once a sweep makes no change, both endpoints of every edge have equal labels; hence every path, and thus every component, has one label. Different components cannot share labels because labels never cross between them. Counting distinct labels therefore counts components, including isolated nodes.

Dry Run

Label Propagation: variable states at each step
Sweep	Edge	Endpoint labels before	Minimum	Labels after	changed after
initial	-	-	-	[0,1,2,3,4]	true to enter loop
1	[0,1]	0,1	0	[0,0,2,3,4]	true
1	[1,2]	0,2	0	[0,0,0,3,4]	true
1	[3,4]	3,4	3	[0,0,0,3,3]	true
2, reset changed	[0,1]	0,0	0	[0,0,0,3,3]	false
2	[1,2]	0,0	0	[0,0,0,3,3]	false
2	[3,4]	3,3	3	[0,0,0,3,3]	false; stop
count labels	0,0,0,3,3	unique {0,3}	-	-	return 2

Complexity Analysis

Time Complexity

O(n + n \cdot e)

Space Complexity

O(n)

Here n is the node count and e is the edge count. Initialization and counting labels cost O(n), even when e = 0. At most n - 1 changing sweeps plus one final unchanged sweep read e edges each. A reverse-ordered chain attains quadratic work with e = n - 1. The label array and set of distinct labels use O(n) auxiliary storage; set insertion has expected constant cost. No adjacency list is built and edges are preserved.

Code

Solution.java

1import java.util.HashSet;2import java.util.Set;3
4class Solution {5    public int countComponents(int n, int[][] edges) {6        int[] label = new int[n];7        for (int i = 0; i < n; i++) {8            label[i] = i;9        }10        boolean changed = true;11        while (changed) {12            changed = false;13            for (int[] e : edges) {14                // Snapshot the minimum before either endpoint changes.15                int low = Math.min(label[e[0]], label[e[1]]);16                if (label[e[0]] != low) {17                    label[e[0]] = low;18                    changed = true;19                }20                if (label[e[1]] != low) {21                    label[e[1]] = low;22                    changed = true;23                }24            }25        }26        Set<Integer> groups = new HashSet<>();27        for (int l : label) {28            groups.add(l);29        }30        return groups.size();31    }32}

Hints

Hint 1

A node with no edges is a component by itself, so start counting from n and work down.

Hint 2

Each edge can merge at most two groups, which suggests tracking merges rather than recounting.

Hint 3

Successful unions equal n minus the component count, so count merges and subtract.

Edge Cases

With no edges the answer is n, including n = 1. Initialization still costs O(n).
A graph can contain a connected group plus isolated nodes: n = 4 and [[0,1]] returns 3.
Cycle edges do not reduce the counter: [[0,1],[1,2],[2,0]] on three nodes returns 1.
Reversing edge endpoints or changing edge order does not change connectivity. Reverse path order can greatly increase label-propagation sweeps.
At the maximum 2000 nodes, a chain connects all nodes; 5000 edges can still leave isolated nodes outside the subgraph they occupy.

Common Mistakes and Interview Tips

Counting only nodes that occur in edges loses isolated components. Start from all n labels or singleton sets.
Subtracting one for every edge undercounts whenever an edge closes a cycle. Decrement only when roots differ.
Comparing immediate parents rather than roots can mistake indirectly connected nodes for separate groups. Always find both representatives.
Stopping label propagation after one sweep depends on edge order and fails on a reverse-ordered chain. Require an entire unchanged sweep.
Treating rank as set size or exact current height after compression leads to incorrect updates. Rank increases only for equal-rank root merges.
Calling the union-find bound strictly linear hides alpha(n). Explain amortized cost and include O(n) initialization for an edgeless graph.

Key Takeaway

Counting groups in undirected graphs is union-find home turf: merge each edge once and read the survivor count.