Overview

This problem involves treating the prerequisite relationships between subjects as a directed graph, and finding a unique course enrollment order following the rule “among all courses that can be taken, always choose the one with the smallest number.”

Analysis

Each prerequisite relationship “\(A \rightarrow B\) (\(A\) must be taken before \(B\))” can be represented as a directed edge \(A \to B\). Then, “courses for which all prerequisites have been completed” correspond to vertices with in-degree (number of unfinished prerequisites) equal to \(0\).

A naive approach of “scanning all courses each time to find those available, then choosing the smallest number among them” requires \(O(N)\) search per step, resulting in \(O(N^2)\) overall, which is too slow for \(N \le 2 \times 10^5\).

Instead, we speed things up by: - Maintaining the “number of unfinished prerequisites (in-degree)” for each course, and - Placing courses whose in-degree becomes \(0\) into a data structure that allows immediate retrieval.

Furthermore, since this problem requires choosing “the smallest number among available courses,” it is natural to manage the set of in-degree \(0\) vertices using a priority queue (min-heap) that can extract the minimum value.

Algorithm

This is topological sort (Kahn’s algorithm) with the added condition of “always choosing the smallest number.”

1. Build the graph as an adjacency list (add edges \(A \to B\)).
2. Count the in-degree \(indeg[i]\) (number of prerequisites) for each vertex.
3. Insert all courses with \(indeg[i]=0\) into a min-heap (these are initially available).
4. Repeat the following until the heap is empty:
   • Extract the course \(v\) with the smallest number from the heap and append it to the answer (take the course).
   • For each edge \(v \to to\), decrement \(indeg[to]\) by \(1\).
   • If \(indeg[to]\) becomes \(0\), that course is now available, so insert it into the heap.
5. The resulting sequence is the desired enrollment order.

Example: When \(1\to3,\ 2\to3\)
Initially, courses \(1\) and \(2\) are available, so the heap is \(\{1,2\}\). Take the minimum \(1\) → then \(2\) → after that \(3\) becomes available, resulting in the order \(1,2,3\).

(In this problem, there are no cycles and it is guaranteed that all courses can be taken, so exactly \(N\) courses are always output.)

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (Each vertex is pushed/popped at most once for \(O(N\log N)\), and processing all edges takes \(O(M)\))
• Space complexity: \(O(N+M)\)
  (For the adjacency list, in-degree array, heap, etc.)

Implementation Notes

• Use heapq (min-heap) to achieve “the smallest number among available courses.”

• Since the input can be up to \(2\times 10^5\) lines, reading all at once with sys.stdin.buffer.read() is faster.

• The graph is managed with an adjacency list g[a].append(b), and in-degrees with indeg[b] += 1.

• By inserting a course into the heap the moment \(indeg[to]\) becomes \(0\) after traversing an edge, we avoid a full scan at each step.

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    g = [[] for _ in range(N + 1)]
    indeg = [0] * (N + 1)

    idx = 2
    for _ in range(M):
        a = data[idx]
        b = data[idx + 1]
        idx += 2
        g[a].append(b)
        indeg[b] += 1

    pq = []
    for i in range(1, N + 1):
        if indeg[i] == 0:
            heapq.heappush(pq, i)

    order = []
    while pq:
        v = heapq.heappop(pq)
        order.append(v)
        for to in g[v]:
            indeg[to] -= 1
            if indeg[to] == 0:
                heapq.heappush(pq, to)

    sys.stdout.write(" ".join(map(str, order)))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.