Number of Connected Components
Given an undirected graph, count the number of connected components.
Constraints:
- 1 <= n <= 2000
- 1 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= edges[i][0] < n
- 0 <= edges[i][1] < n
- edges[i][0] != edges[i][1]
Examples:
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Explanation: There are 2 connected components: [0, 1, 2] and [3, 4].
Solutions
Depth-First Search (DFS)
Time: O(n + m)Space: O(n + m)
We use DFS to traverse the graph and count the number of connected components. We create an adjacency list representation of the graph and then iterate over all nodes. For each unvisited node, we perform a DFS traversal and increment the count of connected components.
function countComponents(n, edges) {
const graph = Array.from(
{
length: n,
},
() => []
);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Set();
let count = 0;
for (let i = 0; i < n; i++) {
if (!visited.has(i)) {
dfs(graph, visited, i);
count++;
}
}
return count;
}
function dfs(graph, visited, node) {
visited.add(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(graph, visited, neighbor);
}
}
}
Follow-up:
How would you solve this problem if the graph is very large and does not fit in memory?
