Neetcode - Number of Connected Components in an Undirected Graph
Own today, build tomorrow.
Number of Connected Components in an Undirected Graph
There is an undirected graph with n nodes. There is also an edges array, where edges[i] = [a, b] means that there is an edge between node a and node b in the graph.
The nodes are numbered from 0 to n - 1.
Return the total number of connected components in that graph.
Input:
n=3
edges=[[0,1], [0,2]]
Output:
1
Input:
n=6
edges=[[0,1], [1,2], [2,3], [4,5]]
Output:
2
This problem is quite similar to the Neetcode - Graph Valid Tree question. The core logic is essentially the same, but the key difference here is that we need to check how many isolated graphs (connected components) can be formed.
In other words, if there are no edges, each node will form its own connected component, resulting in n components. Here's the code:
class Solution {
private:
void dfs(
int node,
map<int, vector<int>> &m,
vector<int> &visited) {
visited[node] = 1;
for (int ngb : m[node]) {
if (visited[ngb]) continue;
dfs(ngb, m, visited);
}
}
public:
int countComponents(int n, vector<vector<int>>& edges) {
if (edges.size() == 0) return n;
map<int, vector<int>> m;
for (const auto &e : edges) {
m[e[0]].push_back(e[1]);
m[e[1]].push_back(e[0]);
}
int count = 0;
vector<int> visited(n, 0);
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(i, m, visited);
++count;
}
}
return count;
}
};DFS - CSY
The core idea is to loop over all nodes and check for any that have not been visited.
Each time we encounter such a node, we increment our counter by 1. That’s essentially the whole logic.
