Problem: BOJ 1766 — Workbook · 한국어 · 日本語
Each directed edge A -> B means problem A must be solved before problem B. We need a topological ordering: every vertex appears exactly once, and every edge points from an earlier position to a later one. When several problems are available, the required ordering chooses the smallest-numbered one first.
Kahn’s algorithm maintains the in-degree (the number of unfinished prerequisites) of each problem. Put every zero-in-degree problem in a min-priority queue. Repeatedly remove the smallest available problem, append it to the answer, and decrement the in-degree of each outgoing neighbor. A neighbor becomes available exactly when its in-degree reaches zero, so insert it then. The heap always chooses the smallest problem that can legally be next; a FIFO queue would not guarantee this. For example, with edges 1 -> 4 and 2 -> 3, after choosing 1, both 2 and 4 are available, and the heap chooses 2 first.
The input may separate integers with any whitespace, so the scanner reads bytes and skips whitespace rather than assuming one record per line. Duplicate edges are retained in both the adjacency list and in-degree count; processing each copy subtracts one, leaving a vertex eligible only after all prerequisite edges have been removed. Isolated problems are in the initial heap, and this also handles N = 1 without special cases.
Building the graph takes O(N + M). Every vertex is inserted into and removed from the heap once, while every edge is processed once, giving O((N + M) log N) time and O(N + M) space.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Main {
private static final class FastScanner {
private final BufferedInputStream in = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int position = 0;
private int length = 0;
private int read() throws IOException {
if (position == length) {
length = in.read(buffer);
position = 0;
if (length == -1) return -1;
}
return buffer[position++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int n = input.nextInt();
int m = input.nextInt();
@SuppressWarnings("unchecked")
ArrayList<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
int[] indegree = new int[n];
for (int i = 0; i < m; i++) {
int from = input.nextInt() - 1;
int to = input.nextInt() - 1;
graph[from].add(to);
indegree[to]++;
}
PriorityQueue<Integer> available = new PriorityQueue<>();
for (int problem = 0; problem < n; problem++) {
if (indegree[problem] == 0) available.add(problem);
}
StringBuilder answer = new StringBuilder();
while (!available.isEmpty()) {
int current = available.remove();
answer.append(current + 1).append(' ');
for (int next : graph[current]) {
if (--indegree[next] == 0) available.add(next);
}
}
System.out.println(answer);
}
}