Facebook PixelNumber of Connected Components in an Undirected Graph — Coding Practice
Number of Connected Components in an Undirected GraphMedium

Number of Connected Components in an Undirected Graph

Medium 5.4k62% acceptance
GraphUnion FindDepth-First Search

You are given n nodes labeled 0 to n - 1 and a list of undirected edges where each entry [a, b] connects node a and node b.

Return the number of connected components in the graph.

Example 1
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Nodes {0,1,2} form one component and {3,4} form another.
Example 2
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Everything is connected into a single chain.
Example 3
Input: n = 4, edges = []
Output: 4
Constraints
  • 1 ≤ n ≤ 2000
  • 0 ≤ edges.length ≤ 5000
  • There are no self-loops or duplicate edges; 0 ≤ a, b < n.
Asked atAmazonGoogleMetaMicrosoft
JavaScript
Loading editor…
Case 1
5, [[0,1],[1,2],[3,4]]
expected: 2
Case 2
5, [[0,1],[1,2],[2,3],[3,4]]
expected: 1
Case 3
4, []
expected: 4
Case 4
1, []
expected: 1
Case 5
6, [[0,1],[2,3],[4,5]]
expected: 3
Case 6
3, [[0,1],[0,2],[1,2]]
expected: 1
Case 7
7, [[0,1],[1,2],[2,0],[3,4]]
expected: 4