C++ 中无向图中连通分量的数量
c++server side programmingprogramming
假设我们有 n 个节点，它们的标签从 0 到 n - 1，并且还给出了一个无向边列表，我们需要定义一个函数来计算无向图中连通分量的数量。
因此，如果输入为 n = 5，边 = [[0, 1], [1, 2], [3, 4]],
则输出为 2
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 dfs()，该函数接受节点、图和一个名为 visitor 的数组作为参数。
如果 visitor[node] 为 false，则 −
visited[node] := true
初始化 i := 0，当 i < graph[node] 的大小时，更新(将 i 增加 1)，执行 −
dfs(graph[node, i], graph, visited)
在 main 方法中执行以下操作 −
定义一个大小为 n 的数组 visitor
如果 n 非零，则 −
定义一个数组 graph[n]
初始化 i := 0，当 i < 边的大小，更新(将 i 加 1)，执行 −
u := edge[i, 0]
v := edge[i, 1]
将 v 插入到 graph[u] 的末尾
将 u 插入到 graph[v] 的末尾
ret := 0
用于初始化 i := 0，当 i < n，更新(将 i 加 1)，执行 −
如果 not visitor[i] 非零，则 −
dfs(i, graph, visitor)
(将 ret 加 1)
return ret
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(int node, vector<int< graph[], vector<bool>& visited){
if(visited[node]) return;
visited[node] = true;
for(int i = 0; i < graph[node].size(); i++){
dfs(graph[node][i], graph, visited);
}
}
int countComponents(int n, vector<vector<int<>& edges) {
vector <bool> visited(n);
if(!n) return 0;
vector <int< graph[n];
for(int i = 0; i < edges.size(); i++){
int u = edges[i][0];
int v = edges[i][1];
graph[u].push_back(v);
graph[v].push_back(u);
}
int ret = 0;
for(int i = 0; i < n; i++){
if(!visited[i]){
dfs(i, graph, visited);
ret++;
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int<> v = {{0,1},{1,2},{3,4}};
cout << (ob.countComponents(5, v));
}
输入
5, [[0,1],[1,2],[3,4]]
输出
2
