문제 41
위상 정렬 순서
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 방향 간선으로 이루어진 그래프가 있다.
모든 정점을 정확히 한 번씩 나열하되, 모든 간선 $(u, v)$에 대해 $u$번 정점이 $v$번 정점보다 앞에 나오도록 하라.
조건을 만족하는 순서가 존재하지 않는다면 CYCLE을 출력한다.
입력
첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000; 0 \le M \le 200\,000)$
두 번째 줄부터 $M$개의 줄에 걸쳐 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v)$
같은 방향 간선은 두 번 이상 주어지지 않는다.
출력
조건을 만족하는 순서가 존재한다면 $N$개의 정점 번호를 순서대로 출력한다.
정점 번호는 공백으로 구분한다. 가능한 정답이 여러 개라면 그중 아무거나 출력한다.
조건을 만족하는 순서가 존재하지 않는다면 CYCLE을 출력한다.
예제 입력 1
6 6 1 4 1 2 2 4 3 4 3 5 4 6
예제 출력 1
1 3 2 5 4 6
예제 입력 2
4 4 1 2 2 3 3 2 3 4
예제 출력 2
CYCLE
공식 해설
간선 $u\to v$가 있으면 $u$가 $v$보다 먼저 나와야 한다. 따라서 아직 남은 정점에서 들어오는 간선이 없는 정점은 다음 순서에 놓을 수 있다.
각 정점의 진입 차수를 구하고 $0$인 정점들을 큐에 넣는다. 큐에서 정점을 꺼내 결과에 추가하고, 그 정점에서 나가는 간선을 제거하듯 도착점의 진입 차수를 줄인다. 새로 $0$이 된 정점도 큐에 넣는다.
정점을 고를 때 모든 선행 정점이 이미 처리되었으므로 결과는 모든 간선의 순서를 지킨다. 반대로 정점이 남았는데 큐가 비었다면 남은 정점마다 다른 남은 정점에서 들어오는 간선이 있다. 이를 계속 거슬러 가면 정점을 반복해서 만나므로 방향 사이클이 존재한다.
따라서 결과에 $N$개가 모두 들어갔으면 그 순서를 출력하고, 아니면 CYCLE을 출력한다. 사이클이 있는 경우 앞에서 고른 정점들을 먼저 출력하지 않도록 결과를 저장해 둔다.
각 정점과 간선을 한 번씩 처리하므로 시간복잡도와 공간복잡도는 $O(N+M)$이다.
구현 · 언어별 풀이
C++ 구현
인접 리스트와 진입 차수 배열, queue<int>를 사용한다. 꺼낸 정점은 vector<int>에 저장하고, 마지막에 크기가 $N$인지 확인한 뒤 순서 또는 CYCLE을 출력한다. 이 문제는 가능한 순서 하나면 되므로 최소 힙은 필요 없다.
C 구현
indegree int 배열과 N칸 배열 큐를 사용한다. 간선을 처리할 때 indegree가 0이 된 정점만 넣는다. 끝난 뒤 출력 후보 수가 N인지 확인하고 사이클이면 부분 순서 대신 지정된 결과를 출력한다.
Python 구현
collections.deque로 indegree 0인 정점을 처리한다. 정렬 순서가 유일할 필요는 없으므로 우선순위 큐를 쓰지 않는다. 처리 수가 N보다 작으면 CYCLE을 출력한다.
Java 구현
ArrayDeque<Integer>로 진입 차수 0인 정점을 탐색한다. 후보 순서를 모은 뒤 개수가 N인지 검사한다. 사이클이 있으면 만들어진 일부 순서를 출력하지 않는다.
Rust 구현
VecDeque<usize>와 Vec<usize> indegree를 사용한다. 실제 간선을 제거할 필요 없이 차수만 줄인다. 모든 정점이 처리됐는지 확인하고 성공한 경우에만 순서를 출력한다.
JavaScript 구현
진입 차수는 Int32Array(n + 1), 큐는 Int32Array(n)와 head/tail로 관리한다. 최초 진입 차수가 $0$인 정점을 모두 넣고, 꺼낸 정점의 간선마다 차수를 하나 줄여 새로 $0$이 된 정점을 넣는다.
사전순 조건은 없으므로 최소 힙이나 큐 전체 정렬은 필요 없다. 결과 배열의 길이가 $N$일 때만 순서를 출력하고, 부족하면 CYCLE만 출력한다. 사이클 판정 전에 부분 결과를 출력하지 않는다.