Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python으로 모든 도시의 모든 도시를 방문할 수 있는지 확인하는 프로그램

<시간/>

[0, n) 범위의 숫자로 표시되는 n개의 도시가 있고 한 도시를 다른 도시로 연결하는 일방통행 도로 목록도 있다고 가정합니다. 어느 도시에서나 갈 수 있는지 확인해야 합니다.

따라서 입력이 n =3과 같으면 도로 =[[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]] , 0에서 1로, 1에서 0으로 갈 수 있으므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

  • dfs() 함수를 정의합니다. 이렇게 하면 i, 방문, g

    가 소요됩니다.
  • 내가 방문한 것으로 표시

  • g[i]의 각 j에 대해 수행

    • j를 방문하지 않으면

      • dfs(j, 방문, g)

  • 함수 travel() 을 정의하십시오. 시간이 걸립니다

  • 방문:=새로운 세트

  • dfs(0, 방문, g)

  • 방문한 크기가 n

    과 같으면 true를 반환합니다.
  • 기본 방법에서 다음을 수행하십시오-

  • 그래프 :=빈 지도

  • rev_graph :=빈 지도

  • 각 출발지 u 및 도로의 목적지 v에 대해 수행

    • 그래프 끝에 v 삽입[u]

    • rev_graph[v]의 끝에 u를 삽입하십시오.

  • travel(graph) 와 travel(rev_graph) 둘 다 참일 때 참 반환

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

예시

class Solution:
   def solve(self, n, roads):
      from collections import defaultdict
         graph = defaultdict(list)
         rev_graph = defaultdict(list)
   for u, v in roads:
      graph[u].append(v)
      rev_graph[v].append(u)
      def dfs(i, visited, g):
      visited.add(i)
   for j in g[i]:
      if j not in visited:
         dfs(j, visited,g)
         def travel(g):
         visited = set()
         dfs(0, visited, g)
      return len(visited)==n
   return travel(graph) and travel(rev_graph)
ob = Solution()
n = 3
roads = [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]
print(ob.solve(n, roads))

입력

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

출력

True