Count Connected Components

A connected component is a group of nodes that can all reach each other. Counting components is the simplest complete graph algorithm: an outer loop over every node, and an inner search that swallows everything reachable.

Given n nodes numbered 0 .. n-1 and a list of undirected edges, return the number of connected components.

Examples

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

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

Constraints

• 1 <= n <= 2000
• 0 <= len(edges) <= 5000, no duplicate edges
• Target: O(n + E) time

Goals

• Traverse a graph with DFS or BFS using a visited set
• Use the 'start a new search from every unvisited node' loop to count components
• Build an adjacency list from an edge list as a first step