数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中无向图连通分量的数量
假设我们有n个节点，它们从0到n-1标记，并且还给定了一个无向边的列表，我们需要定义一个函数来查找无向图中连通分量的数量。
因此，如果输入类似于n=5，edges=[[0, 1], [1, 2], [3, 4]]，
则输出将为2
为了解决这个问题，我们将遵循以下步骤：
定义一个函数dfs()，它将接收节点、图和一个名为visited的数组作为参数，
如果visited[node]为假，则：
visited[node] := true
对于初始化i:=0，当i < graph[node]的大小，更新（i增加1），执行：
dfs(graph[node, i], graph, visited)
从主方法执行以下操作：
定义一个大小为n的数组visited
如果n不为零，则：
定义一个数组graph[n]
对于初始化i:=0，当i < edges的大小，更新（i增加1），执行：
u := edges[i, 0]
v := edges[i, 1]
在graph[u]的末尾插入v
在graph[v]的末尾插入u
ret := 0
对于初始化i:=0，当i < n，更新（i增加1），执行：
如果visited[i]不为零，则：
dfs(i, graph, visited)
（ret增加1）
返回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
更新于: 2020年11月18日
2K+ 浏览量
广告