[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