파이썬에서 홀수 길이 사이클이 그래프에 있는지 확인하는 프로그램

무방향 그래프가 있다고 가정하고 그 안에 홀수 길이의 사이클을 찾을 수 있는지 여부를 확인해야 합니다.

따라서 입력이 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 - 경로[노드])가 홀수인 경우 true를 반환
• 노드를 방문하면
  • 거짓을 반환
• 노드를 방문한 것으로 표시
• 경로[노드] :=나
• arr[노드]의 각 c에 대해 다음을 수행합니다.
  • dfs(c, i + 1)가 참이면
    • 참 반환
• 델 경로[노드]
• 거짓을 반환
• 메인 방법에서 다음을 수행하십시오 -
• 방문함 :=새 세트, 경로 :=새 지도
• 0에서 arr 크기의 범위에 있는 i에 대해 수행
• dfs(i, 0)가 참이면
• 참 반환
• 거짓을 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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