Number of Connected Components

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.

Function signature

func CountComponents(n int, edges [][]int) int

Examples

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Explanation:
    0---1---2   3---4
Two components: {0,1,2} and {3,4}

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Explanation: All nodes are connected.
    0---1---2---3---4

Example 3:

Input: n = 4, edges = []
Output: 4
Explanation: No edges, so each node is its own component.

Constraints

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

Hints

1. Use Union-Find to efficiently merge connected nodes.
2. Start with n components, decrease count each time a union merges two different components.
3. Alternative: Use DFS/BFS to count connected components.

Notes

• This is a classic application of Union-Find.
• Each successful union reduces the component count by 1.
• Time complexity with path compression and union by rank: O(n + m * α(n)) ≈ O(n + m)