총 n개의 코스가 있다고 가정하고 0에서 n-1까지 레이블이 지정됩니다. 일부 코스에는 선행 조건이 있을 수 있습니다. 총 코스 수와 선행 조건 쌍 목록이 주어지면 모든 코스를 완료하기 위해 수강해야 하는 코스 순서를 찾아야 합니다. 올바른 주문이 여러 개 있을 수 있으며 그 중 하나만 찾으면 됩니다. 모든 과정을 마치는 것이 불가능한 경우 빈 배열을 반환하십시오.
따라서 입력이 2, [[1, 0]]과 같으면 결과는 [0,1]이 됩니다. 총 2과목을 수강하실 수 있습니다. 1번 과정을 수강하려면 0번 과정을 마쳐야 합니다. 따라서 올바른 과정 순서는 [0,1]
입니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
기본 방법에서는 numCourses와 전제 조건이 필요합니다. 이것은 다음과 같이 작동합니다. -
-
in_degree라는 배열을 정의하고 모든 노드의 각도를 모두 채우고 adj :=그래프의 인접 목록
-
방문이라는 하나의 배열을 정의하고 0으로 채우십시오. 크기는 numCourses와 동일합니다.
-
하나의 빈 스택을 정의합니다.
-
0 ~ numCourses
범위의 i에 대해-
방문[i]이 false이고 노드 i의 dfs가 스택을 전달하여 false인 경우
-
빈 목록을 반환
-
-
-
스택 요소를 역순으로 반환합니다.
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class Solution(object):
def findOrder(self, numCourses, prerequisites):
in_degree,adj=self.create_adj(numCourses,prerequisites)
visited = [0 for i in range(numCourses)]
stack = []
for i in range(numCourses):
if not visited[i] and not self.dfs(i,visited,stack,adj):
return []
return stack[::-1]
def create_adj(self,n,graph):
adj = {}
in_degree= [0 for i in range(n)]
for i in graph:
in_degree[i[0]]+=1
if i[1] in adj:
adj[i[1]].append(i[0])
else:
adj[i[1]] = [i[0]]
return in_degree,adj
def dfs(self, node, visited,stack,adj):
if visited[node] == -1:
return False
if visited[node] == 1:
return True
visited[node] = -1
if node in adj:
for i in adj[node]:
if not self.dfs(i,visited,stack,adj):
return False
visited[node]=1
stack.append(node)
return True
ob = Solution()
print(ob.findOrder(2, [[1,0]])) 입력
2 [[1,0]]
출력
[0,1]