与えられたグラフをチェックするプログラムは、Pythonではツリーのセットであるかどうか

エッジのリストとして表されるグラフがあるとします。グラフが木（森）の集まりであるかどうかを確認する必要があります。

したがって、入力が次のような場合

その場合、出力はTrueになります

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

• 関数dfs（）を定義します。これはノードを取ります、前へ

• ノードが表示されている場合、

  • Falseを返す

• 見られるにノードを挿入する

• e [node]内の隣接するノードnごとに、実行

  • nがprevと同じでない場合、

    • dfs（n、node）がfalseの場合、

      • Falseを返す

• Trueを返す

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

• e：=空の地図

• エッジの開始ノードuと終了ノードvごとに、実行します

  • e [u]

    の最後にvを挿入します

  • e [v]

    の最後にuを挿入します

• 見た：=新しいセット

• eのノードごとに、次のようにします

  • ノードが表示されず、dfs（node、-1）がfalseの場合、

    • Falseを返す

• Trueを返す

理解を深めるために、次の実装を見てみましょう-

例

from collections import defaultdict
class Solution:
   def solve(self, edges):
      e = defaultdict(list)
      for t,f in edges:
         e[t].append(f)
         e[f].append(t)

      seen = set()

      def dfs(node, prev):
         if node in seen:
            return False
         seen.add(node)
      for adj in e[node]:
         if adj != prev:
            if not dfs(adj, node):
               return False
      return True

   for node in e:
      if node not in seen and not dfs(node, -1):
         return False
   return True

ob = Solution()
edges = [[0, 1],[0, 2],[4, 3]]
print(ob.solve(edges))

入力

[[0, 1],[0, 2],[4, 3]]

出力

True