7236 : 위상 정렬 기초
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 과목과 $M$개의 선수과목 관계가 주어질 때, 수강 가능한 순서를 위상 정렬(Topological Sort)로 구하십시오.
순환이 존재하면
답이 여러 개라면 과목 번호가 사전순으로 가장 앞서는 순서를 출력합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
순환이 존재하면
IMPOSSIBLE을 출력합니다.답이 여러 개라면 과목 번호가 사전순으로 가장 앞서는 순서를 출력합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 과목 수 $N$과 선수 관계 수 $M$이 주어집니다. ($1 \le N \le 1{,}000$, $1 \le M \le 3{,}000$)
이어서 $M$개의 줄에 선수과목 정보 $u$, $v$가 주어집니다. ($u$를 이수해야 $v$를 수강 가능)
이어서 $M$개의 줄에 선수과목 정보 $u$, $v$가 주어집니다. ($u$를 이수해야 $v$를 수강 가능)
출력 설명
수강 가능한 순서대로 과목 번호를 공백으로 구분하여 출력합니다.
답이 여러 개라면 사전순으로 가장 앞서는 순서를 출력합니다.
순환이 존재하면
답이 여러 개라면 사전순으로 가장 앞서는 순서를 출력합니다.
순환이 존재하면
IMPOSSIBLE을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2
1 3
2 4
3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 4도움
진입차수(in-degree)가 0인 노드를 최솟값 기준 우선순위 큐에 넣고, 하나씩 꺼내며 연결된 노드의 진입차수를 줄입니다. 최종 결과 노드 수가 $N$보다 적으면 순환이 존재합니다.