数据结构
网络
关系型数据库管理系统 (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 次浏览
广告