資料結構
網路
關係資料庫管理系統
作業系統
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+ 瀏覽量
廣告