BOJ. Final Ranking (3665)

[Link] https://www.acmicpc.net/problem/3665 · 한국어 · 日本語

The previous year’s ranking gives a complete order: for every pair of teams, the higher-ranked team has a directed edge to the lower-ranked team. Each reported change reverses exactly one edge. Updating both the adjacency matrix and the destination’s indegree keeps the graph ready for topological sorting.

Kahn’s algorithm repeatedly removes a team whose indegree is zero. If more than one team is available at any step, there are multiple possible next teams, so the final ranking is ambiguous. If fewer than N teams can be removed, the changed comparisons contain a cycle and no ranking exists. A cycle takes precedence over ambiguity: print IMPOSSIBLE if the process does not output every team; otherwise print ? when any step had multiple choices, and print the ordering only when every step was forced.

The initial graph has N(N - 1) / 2 edges. Building it and scanning every possible edge during Kahn’s algorithm take O(N²) time; processing the M reversals takes O(M), for O(N² + M) total time and O(N²) space.

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayDeque;

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

        while (testCases-- > 0) {
            int n = input.nextInt();
            int[] previous = new int[n];
            for (int i = 0; i < n; i++) {
                previous[i] = input.nextInt() - 1;
            }

            boolean[][] edge = new boolean[n][n];
            int[] indegree = new int[n];
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    edge[previous[i]][previous[j]] = true;
                    indegree[previous[j]]++;
                }
            }

            int changes = input.nextInt();
            for (int i = 0; i < changes; i++) {
                int a = input.nextInt() - 1;
                int b = input.nextInt() - 1;
                if (edge[a][b]) {
                    edge[a][b] = false;
                    edge[b][a] = true;
                    indegree[b]--;
                    indegree[a]++;
                } else {
                    edge[b][a] = false;
                    edge[a][b] = true;
                    indegree[a]--;
                    indegree[b]++;
                }
            }

            ArrayDeque<Integer> queue = new ArrayDeque<>();
            for (int team = 0; team < n; team++) {
                if (indegree[team] == 0) {
                    queue.addLast(team);
                }
            }

            int[] ranking = new int[n];
            int count = 0;
            boolean ambiguous = false;
            while (!queue.isEmpty()) {
                if (queue.size() > 1) {
                    ambiguous = true;
                }
                int team = queue.removeFirst();
                ranking[count++] = team;
                for (int next = 0; next < n; next++) {
                    if (edge[team][next] && --indegree[next] == 0) {
                        queue.addLast(next);
                    }
                }
            }

            if (count < n) {
                answer.append("IMPOSSIBLE\n");
            } else if (ambiguous) {
                answer.append("?\n");
            } else {
                for (int team : ranking) {
                    answer.append(team + 1).append(' ');
                }
                answer.setLength(answer.length() - 1);
                answer.append('\n');
            }
        }

        System.out.print(answer);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);

        int nextInt() throws IOException {
            int value = 0;
            int c;
            do {
                c = input.read();
            } while (c <= ' ' && c != -1);
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = input.read();
            }
            return value;
        }
    }
}