資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++實現圖的有效樹驗證
假設我們有n個節點，它們從0到n-1編號，以及一個無向邊的列表[u,v]，我們需要定義一個函式來檢查這些邊是否構成一棵有效的樹。
因此，如果輸入類似於n = 5，edges = [[0,1], [0,2], [0,3], [1,4]]，則輸出為true。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式dfs()，它將接收節點、父節點、圖和另一個名為visited的陣列作為引數。
如果visited[node]等於1，則：
返回true
如果visited[node]等於2，則：
返回false
visited[node] := 2
ret := true
對於i從0到graph[node]的大小，執行：
如果graph[node, i]不等於par，則：
ret := ret AND dfs(graph[node, i], node, graph, visited)
visited[node] := 1
返回ret
在主方法中執行以下操作：
定義一個大小為n的visited陣列，並將其填充為0。
定義一個大小為n的列表列表graph。
對於i從0到edges的大小，執行：
u := edges[i, 0], v := edges[i, 1]
將v插入到graph[u]的末尾
將u插入到graph[v]的末尾
如果dfs(0, -1, graph, visited)為false，則：
返回false
對於i從0到n，執行：
如果visited[i]為零，則：
返回false
返回true
示例
讓我們看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool dfs(int node, int par, vector <int< graph[], vector <int<& visited){
if (visited[node] == 1)
return true;
if (visited[node] == 2)
return false;
visited[node] = 2;
bool ret = true;
for (int i = 0; i < graph[node].size(); i++) {
if (graph[node][i] != par)
ret &= dfs(graph[node][i], node, graph, visited);
}
visited[node] = 1;
return ret;
}
bool validTree(int n, vector<vector<int<>& edges) {
vector<int< visited(n, 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);
}
if (!dfs(0, -1, graph, visited))
return false;
for (int i = 0; i < n; i++) {
if (!visited[i])
return false;
}
return true;
}
};
main(){
Solution ob;
vector<vector<int<> v = {{0,1},{0,2},{0,3},{1,4}};
cout << (ob.validTree(5,v));
}輸入
5, {{0,1},{0,2},{0,3},{1,4}}輸出
1
更新於：2020年11月18日
241 次瀏覽
廣告