Module: 토폴로지 정렬


Problem

1 /5


토폴로지 정렬

Theory Click to read/hide

알고리즘은 다음과 같이 설명할 수 있습니다.
n개의 꼭지점과 m개의 모서리가 있는 유향 그래프가 주어집니다. 각 가장자리가 낮은 번호의 정점에서 높은 번호의 정점으로 이어지는 방식으로 정점의 번호를 다시 지정해야 합니다.
즉, 그래프의 모든 모서리에 의해 주어진 순서에 해당하는 정점의 순열(위상적 순서)을 찾아야 합니다.
깊이 우선 검색(dfs(v))
을 사용합니다.
\(dfs(v)\) 에서 종료할 때 목록의 시작 부분에 정점을 추가하면 끝 이 목록에서 토폴로지 정렬을 얻습니다.
따라서 원하는 토폴로지 정렬 — 종료 시간의 내림차순으로 정렬됩니다.

Problem

가중치가 없는 방향성 그래프가 주어집니다. 이를 위상학적으로 정렬해야 합니다.

입력: 첫 번째 줄에는 두 개의 자연수 n과 m이 포함됩니다(1≤n≤105, 1≤m≤10< sup >5) — 그래프의 정점과 모서리의 수. 다음 m 줄은 그래프의 가장자리를 나열합니다. 각 모서리는 한 쌍의 숫자로 표시됩니다. 각각 시작 및 끝 정점의 번호입니다.
 
출력: 그래프의 모든 토폴로지 정렬을 정점 번호 시퀀스로 인쇄합니다. 그래프를 위상적으로 정렬할 수 없으면 -1을 인쇄합니다.
첫 번째 줄에는 정점 N과 가장자리 M의 수가 포함됩니다. 

<헤드> <일># <몸>
입력 출력
1 4 4
14
4 3
4 2
3 2
1 4 3 2