Watch 10 video solutions for Number of Connected Components in an Undirected Graph, a medium level problem involving Depth-First Search, Breadth-First Search, Union Find. This walkthrough by NeetCode has 257,758 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi 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
Constraints:
1 <= n <= 20001 <= edges.length <= 5000edges[i].length == 20 <= ai <= bi < nai != biProblem Overview: You are given n nodes labeled from 0 to n-1 and a list of undirected edges. The task is to determine how many connected components exist in the graph. A connected component is a group of nodes where every node is reachable from any other node in that group.
Approach 1: Graph Traversal using DFS/BFS (O(n + m) time, O(n + m) space)
Build an adjacency list from the edge list, then traverse the graph. Iterate through every node. If a node has not been visited, start a traversal (either Depth-First Search or Breadth-First Search) from that node and mark all reachable nodes as visited. Each time you start a new traversal, you have discovered a new connected component. The adjacency list takes O(n + m) space where m is the number of edges. The traversal visits each node and edge once, giving O(n + m) time complexity. This approach works well when you already represent the graph explicitly and want a clear traversal-based solution.
Approach 2: Union-Find / Disjoint Set (O(n + m · α(n)) time, O(n) space)
The Union-Find data structure groups nodes into sets representing components. Initially, every node is its own parent. For each edge (u, v), perform a union(u, v) operation to merge their sets. Use path compression and union by rank to keep the structure shallow. After processing all edges, the number of distinct roots equals the number of connected components. The amortized cost of each operation is nearly constant, α(n) (inverse Ackermann function). This approach avoids building adjacency lists and is particularly efficient when edges arrive incrementally or when solving multiple connectivity queries.
Both strategies rely on the same insight: nodes belong to the same component if there exists a path between them in the graph. Traversal explicitly explores that path structure, while Union-Find tracks connectivity through set merges.
Recommended for interviews: DFS or BFS traversal is the most commonly expected solution because it demonstrates understanding of graph representation and traversal. Union-Find is also highly valued since it shows familiarity with a powerful connectivity data structure. A candidate who can explain both approaches and their tradeoffs shows strong graph fundamentals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS/BFS Graph Traversal | O(n + m) | O(n + m) | General graph problems when adjacency lists are easy to build and you want explicit traversal |
| Union-Find (Disjoint Set) | O(n + m · α(n)) | O(n) | Connectivity problems, dynamic edge additions, or when avoiding adjacency lists |