用 C++ 绘制有效树
假设我们有 n 个节点，它们的标签从 0 到 n-1，以及一个无向边列表 [u,v]，我们必须定义一个函数来检查这些边是否构成有效树。
因此，如果输入为 n = 5，并且边 = [[0,1], [0,2], [0,3], [1,4]]，则输出将为 true
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 dfs()，它将采用 node、par、graph 和另一个名为 accessed 的数组，
如果 accessed[node] 与 1 相同，则 −
return true
如果visited[node] 与 2 相同，则 −
返回 false
visited[node] := 2
ret := true
初始化 i := 0，当 i < graph[node] 的大小时，更新(将 i 增加 1)，执行 −
如果 graph[node, i] 不等于 par，则 −
ret := ret AND dfs(graph[node, i], node, graph, visited)
visited[node] := 1
return ret
从 main 方法执行以下操作 −
定义一个大小为 n 的访问数组并用 0 填充。
定义一个名为 graph 的大小为 n 的列表列表
初始化 i := 0，当 i <边的大小，更新(将 i 增加 1)，执行 −
u := edge[i, 0], v := edge[i, 1]
在 graph[u] 末尾插入 v
在 graph[v] 末尾插入 u
如果 dfs(0, -1, graph, visits) 为 false，则 −
返回 false
对于初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
如果 visits[i] 为零，则 −
return false
return 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
