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.
class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
vector<vector<int>> graph(n);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
vector<bool> visited(n, false);
int count = 0;
for (int i = 0;
i < n;
i++) {
if (!visited[i]) {
dfs(graph, visited, i);
count++;
}
}
return count;
}
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
visited[node] = true;
for (int neighbor : graph[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?
