Graph BFS / DFS
LC #323Medium
Number of Connected Components in Undirected Graph
Graph BFS / DFS
LinkedInGoogleAmazonProblem
Given n nodes and a list of edges forming an undirected graph, return the number of connected components.
graphunion-finddfsbfs
Constraints
- ›1 ≤ n ≤ 2000
- ›1 ≤ edges.length ≤ 5000
- ›No duplicate edges
- ›No self-loops
Example
Input
n = 5, edges = [[0,1],[1,2],[3,4]]Output
2Why
Component 1: {0,1,2}. Component 2: {3,4}. Total = 2 components.