Mid/Senior
Number of Connected Components in an Undirected Graph
You have an undirected graph with n nodes labeled from 0 to n - 1.
You are given an integer n and an array edges, where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi.
Return the number of connected components in the graph.
A connected component is a group of nodes where every pair of nodes is connected by some path, and no node in the group is connected to any node outside the group.
Example 1
Input
n = 5, edges = [[0,1],[1,2],[3,4]]Output
2Nodes 0, 1, and 2 form one component, and nodes 3 and 4 form another component.
Example 2
Input
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]Output
1All nodes are connected through the chain of edges, so there is only one component.
Constraints
- 1 <= n <= 2000
- 0 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- There are no repeated edges.