Pythonで奇数の長さのサイクルがグラフにあるかどうかを確認するプログラム

無向グラフがあり、その中に奇数の長さのサイクルが見つかるかどうかを確認する必要があるとします。

したがって、入力がadj_list =[[1、2]、[0、3、4]、[0、3、4]、[1、2、4]、[1、2、3]]

[0、1、3、4、2]、[1、3、4]、[2、3、4]のような奇数の長さのサイクルがあるため、出力はTrueになります。

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

• 関数dfs（）を定義します。これはノードを取ります、私
• ノードがパス内にある場合、
  • （i --path [node]）が奇数の場合はtrueを返します
• ノードにアクセスした場合、
  • Falseを返す
• ノードを訪問済みとしてマーク
• path [node]：=i
• arr [node]のcごとに、
  を実行します。
  • dfs（c、i + 1）が真の場合、
    • Trueを返す
• del path [node]
• Falseを返す
• メインの方法から次のようにします-
• 訪問：=新しいセット、パス：=新しいマップ
• 0からarrのサイズの範囲のiの場合は、実行してください
• dfs（i、0）がtrueの場合、
• Trueを返す
• Falseを返す

例（Python）

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

class Solution:
   def solve(self, arr):
      def dfs(node, i):
         if node in path:
            return (i - path[node]) % 2 == 1
         if node in visited:
            return False
         visited.add(node)
         path[node] = i
         for c in arr[node]:
            if dfs(c, i + 1):
               return True
         del path[node]
         return False
      visited, path = set(), {}
      for i in range(len(arr)):
         if dfs(i, 0):
            return True
      return False
ob = Solution()
adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
print(ob.solve(adj_list))

入力

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

出力

True