위상 정렬과 사이클 판별

왜 이 문제를 푸나요?

작업 순서·선수 과목처럼 선후 관계가 있는 문제를 해결하는 표준 알고리즘입니다. 정렬 결과를 만드는 동시에 사이클도 판별하는 방법을 익힙니다.

정점 수 n과 방향 간선 [선행, 후행] 목록이 주어집니다. 선후 관계를 만족하는 위상 정렬 결과를 반환하세요. 동시에 선택 가능한 정점 중 번호가 가장 작은 정점을 먼저 선택하고, 사이클이 있으면 빈 리스트를 반환합니다.

topological_sort(n, edges)

최소 힙 사용 시 O((V+E) log V)

실행하면 아래 순서대로 채점합니다. print() 출력도 이 순서대로 쌓입니다.

#	이름	`n`	`edges`	기대값
1	여러 시작점	`6`	`[[0, 2], [1, 2], [1, 3], [2, 4], [3, 4]]`	`[0, 1, 2, 3, 4, 5]`
2	일직선	`4`	`[[2, 0], [0, 3], [3, 1]]`	`[2, 0, 3, 1]`
3	사이클	`3`	`[[0, 1], [1, 2], [2, 0]]`	`[]`
4	간선 없는 그래프	`4`	`[]`	`[0, 1, 2, 3]`
5	합류 의존성	`5`	`[[0, 2], [1, 2], [2, 3], [2, 4]]`	`[0, 1, 2, 3, 4]`

Python 표준 라이브러리는 사용할 수 있습니다. 함수 이름과 매개변수는 제시된 형태를 유지하세요.