图连通区域的个数
时间: 2023-07-23 14:09:14 浏览: 42
要求你给出一个图的连通区域的个数,这个问题可以通过深度优先搜索或广度优先搜索来解决。
具体的做法是,从图中的任意一个节点开始,对它进行深度优先搜索或广度优先搜索,将与它相邻的节点标记为已访问,并继续对这些节点进行搜索。当搜索结束后,将搜索到的所有节点标记为已访问,然后开始下一次搜索,直到所有的节点都被访问过。
在搜索的过程中,可以使用一个计数器来记录搜索到的连通区域的个数。
代码实现如下(以深度优先搜索为例):
```
int countConnectedComponents(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
count++;
dfs(graph, visited, i);
}
}
return count;
}
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int u) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(graph, visited, v);
}
}
}
```
其中,`graph` 表示图的邻接表,`visited` 表示节点是否被访问过。