BOJ. Line up (2252)

[Problem] https://www.acmicpc.net/problem/2252

Each input pair A B means that student A must stand before student B. Model this rule as a directed edge A -> B. A valid line is a topological ordering: every edge points from an earlier student to a later one. Students with no ordering relationship can appear in either order, so the result is one valid ordering, not necessarily a unique one.

Kahn’s algorithm repeatedly selects a vertex with indegree zero (no remaining prerequisite), outputs it, and removes its outgoing edges. Removing an edge decreases the indegree of its destination; when that value reaches zero, the destination is ready to be output. The queue can contain any number of ready vertices, and every choice preserves the required partial order.

Store every input edge in the adjacency list and increment its destination’s indegree for every occurrence. This keeps the two representations consistent even if a constraint is repeated. For a DAG, every vertex is eventually output exactly once. The algorithm takes O(N + M) time and O(N + M) space, where N is the number of students and M is the number of constraints.

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int studentCount = input.nextInt();
        int constraintCount = input.nextInt();

        List<List<Integer>> next = new ArrayList<>(studentCount);
        for (int student = 0; student < studentCount; student++) {
            next.add(new ArrayList<>());
        }

        int[] indegree = new int[studentCount];
        for (int i = 0; i < constraintCount; i++) {
            int before = input.nextInt() - 1;
            int after = input.nextInt() - 1;
            next.get(before).add(after);
            indegree[after]++;
        }

        Queue<Integer> ready = new ArrayDeque<>();
        for (int student = 0; student < studentCount; student++) {
            if (indegree[student] == 0) {
                ready.offer(student);
            }
        }

        StringBuilder output = new StringBuilder();
        boolean first = true;
        while (!ready.isEmpty()) {
            int student = ready.poll();
            if (!first) {
                output.append(' ');
            }
            output.append(student + 1);
            first = false;

            for (int after : next.get(student)) {
                indegree[after]--;
                if (indegree[after] == 0) {
                    ready.offer(after);
                }
            }
        }

        System.out.println(output);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int position;
        private int length;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[position++];
        }

        private 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;
        }
    }
}