Number of Connected Components in an Undirected Graph
Medium
Depth-First Search
Breadth-First Search
Union Find
Graph
You have a graph of `n` nodes. You are given an integer `n` and an array `edges` where `edges[i] = [aᵢ, bᵢ]` indicates that there is an edge between `aᵢ` and `bᵢ` in the graph. Return *the number of connected components in the graph*.
Example 1
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Example 2
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Example 3
Input: n = 4, edges = []
Output: 4

Constraints

  • •1 <= n <= 2000
  • •1 <= edges.length <= 5000
  • •edges[i].length == 2
  • •0 <= aᵢ, bᵢ < n
  • •aᵢ != bᵢ
  • •There are no repeated edges.
Time Complexity
O(V+E)
Space Complexity
O(V+E)
14
Case 1
Input: 5 [[0,1],[1,2],[3,4]]
Expected: 2
Case 2
Input: 5 [[0,1],[1,2],[2,3],[3,4]]
Expected: 1
Case 3
Input: 4 []
Expected: 4