주어진 그래프를 확인하는 프로그램은 Python에서 트리 집합인지 여부

간선 목록으로 표시된 그래프가 있다고 가정합니다. 그래프가 나무(숲)의 집합인지 확인해야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 True

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• dfs() 함수를 정의합니다. 이것은 노드가 필요합니다. 이전

• 노드가 표시되면

  • 거짓을 반환

• 노드 삽입

• e[node]의 각 인접 노드 n에 대해 수행

  • n이 이전과 같지 않으면

    • dfs(n, node)가 거짓이면

      • 거짓을 반환

• 참을 반환

• 기본 방법에서 다음을 수행하십시오 -

• e :=빈 지도

• 가장자리의 각 시작 노드 u와 끝 노드 v에 대해 다음을 수행합니다.

  • e[u]

    끝에 v 삽입

  • e[v]

    끝에 u를 삽입합니다.

• 본 :=새로운 세트

• e의 각 노드에 대해 수행

  • 노드가 보이지 않고 dfs(node, -1)가 거짓이면

    • 거짓을 반환

• 참을 반환

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

예시

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