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.
public int countComponents(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0;
i < n;
i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0;
i < n;
i++) {
if (!visited[i]) {
dfs(graph, visited, i);
count++;
}
}
return count;
}
public void dfs(List<List<Integer>> graph, boolean[] visited, int node) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[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?
