在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：= ret AND dfs（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