Number of Connected Components in an Undirected Graph

Problem

You have n nodes labelled 0 through n - 1 and a list of undirected edges. Return how many connected components the graph has, counting isolated nodes as components of size one.

• There are at most 3,000 nodes and at most 8,000 edges.
• Edges are unordered pairs of distinct nodes; no duplicates.

Examples

• n = 6, edges = [[0,1],[1,2],[3,4]] → 3. {0,1,2}, {3,4}, and the isolated node 5.
• n = 6, edges = [[0,1],[1,2],[2,3],[3,4],[4,5]] → 1. A single path through all six nodes.
• n = 4, edges = [] → 4. Every node is its own component.

Hints

1. Start with every node in its own group. What happens to the number of groups when you process an edge between two nodes that are already in the same group?
2. You need "which group is this node in" and "merge two groups" to be fast.
3. Union-find: begin with n components, and decrement the count each time a union actually merges two different sets. Alternatively, DFS/BFS from each unvisited node and count the starts.