在C ++中绘制有效树图
假设我们有n个节点，它们被标记为从0到n-1，并列出了无向边[u，v]的列表，我们必须定义一个函数来检查这些边是否构成了有效的树。
因此，如果输入像n=5，并且边沿=[[0,1]，[0,2]，[0,3]，[1,4]]，那么输出将为true
为了解决这个问题，我们将遵循以下步骤-
定义一个函数dfs()，它将使用节点，参数，图和另一个称为Visited的数组，
如果visited[node]与1相同，则-
返回真
如果visited[node]与2相同，则-
返回假
visit[node]：=2
ret：=true
对于初始化i：=0，当i<graph[node]的大小时，更新（将i增加1），执行-
ret：=retANDdfs（graph[node，i]，node，graph，visited）
如果graph[node，i]不等于par，则-
Visited[node]：=1
返回ret
从主要方法中执行以下操作-
定义一个大小为n的访问数组，并用0填充。
定义一个列表列表，称为大小为n的图
对于初始化i：=0，当i<边的大小时，更新（将i增加1），执行-
u：=edges[i，0]，v：=edges[i，1]
在图形的末尾插入v[u]
在图形[v]的末尾插入u
如果dfs(0,-1,graph,Visited)为假，则-
返回假
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
返回假
如果visit[i]为零，则-
返回真
例
让我们看下面的实现以更好地理解-
#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