Connected Components in an Undirected Graph

You are given n nodes labeled from 0 to n - 1 and an undirected edge list edges. Return how many connected components the graph contains.

A connected component is a maximal group of nodes where every node can reach every other node in the same group by following edges.

Input / output

• Input: n: int, edges: int[][]
• Output: integer component count

Examples

1. n = 5, edges = [[0,1],[1,2],[3,4]] returns 2.
2. n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] returns 1.
3. n = 4, edges = [] returns 4 because every node is isolated.

Constraints

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= a, b < n and a != b
• There are no duplicate edges

Target complexity

• Aim for near-linear O(n + edges.length * α(n)) time and O(n) extra space.

Hints

1. Every time you connect two previously separate groups, the total number of components drops by one.
2. A disjoint-set union (union-find) structure lets you merge groups without re-running a full DFS after each edge.

Follow-up If edges were streamed one by one and you needed the component count after each insertion, which approach would you prefer and why?