Number of Connected Components in an Undirected Graph
MediumGraphs
You have n nodes labelled 0 to n - 1 and a list of undirected edges, where edges[i] = [a, b] connects nodes a and b.
A connected component is a maximal group of nodes in which every node can reach every other through edges. Return the number of connected components. A node with no edges forms a component on its own.
Example 1
- Input:
- n = 7, edges = [[0, 1], [1, 2], [3, 4], [6, 5]]
- Output:
- 3
- Explanation
- The components are {0, 1, 2}, {3, 4} and {5, 6}, so the answer is 3.
Example 2
- Input:
- n = 4, edges = [[0, 1], [1, 2], [2, 0]]
- Output:
- 2
- Explanation
- Nodes 0, 1 and 2 form a triangle, which is one component. Node 3 has no edges, so it is a second component.
Example 3
- Input:
- n = 3, edges = []
- Output:
- 3
- Explanation
- With no edges at all, each of the 3 nodes is its own component.
Constraints
1 <= n <= 20000 <= edges.length <= 5000edges[i].length == 20 <= a, b < nanda != b- There are no repeated edges