C++で有効なツリーをグラフ化する

0からn-1までのラベルが付けられたn個のノードと、無向エッジのリスト[u、v]があるとします。これらのエッジが有効なツリーを構成しているかどうかをチェックする関数を定義する必要があります。

したがって、入力がn =5で、edges =[[0,1]、[0,2]、[0,3]、[1,4]]の場合、出力はtrueになります

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これにより、ノード、パー、グラフ、およびvisitedと呼ばれる別の配列が取得されます

• visited [node]が1と同じ場合、-

  • trueを返す

• visited [node]が2と同じ場合、-

  • falseを返す

• 訪問済み[ノード]：=2

• ret：=true

• 初期化i：=0の場合、i <グラフ[ノード]のサイズの場合、更新（iを1増やします）、実行-

  • graph [node、i]がparと等しくない場合、-

    • ret：=ret AND dfs（graph [node、i]、node、graph、visited）

• 訪問済み[ノード]：=1

• retを返す

• メインの方法から、次のようにします-

• サイズnの訪問済み配列を定義し、これを0で埋めます。

• サイズnのグラフと呼ばれるリストのリストを定義します

• 初期化i：=0の場合、i <エッジのサイズの場合、更新（iを1増やします）、実行-

  • u：=エッジ[i、0]、v：=エッジ[i、1]

  • グラフの最後にvを挿入します[u]

  • グラフの最後にuを挿入します[v]

• dfs（0、-1、graph、visited）がfalseの場合、-

  • falseを返す

• 初期化i：=0の場合、i

  • 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