Overview

This problem requires performing a topological sort while selecting subjects in order of smallest number, given prerequisite conditions.

Analysis

If we construct a graph with prerequisites as directed edges, it becomes a Directed Acyclic Graph (DAG). At each step, “subjects for which all prerequisites have been completed” corresponds to nodes with in-degree 0 in the graph. Since the problem requires selecting the one with the smallest number among these, we need a data structure that can efficiently extract the minimum element, rather than a simple queue.

A naive approach would be to scan all subjects with in-degree 0 at each step and select the minimum, but this results in a time complexity of \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\).

Algorithm

This problem can be efficiently solved using “topological sort with a priority queue.” The specific steps are as follows:

1. Represent the graph as an adjacency list and prepare an array to manage the in-degree of each node
2. Add all nodes with in-degree 0 to a priority queue (min-heap)
3. Repeat the following until the queue is empty:
   • Extract the minimum element from the queue and add it to the result list
   • Decrease the in-degree of all nodes reachable via outgoing edges from that node by 1
   • Add any nodes whose in-degree becomes 0 to the priority queue

This allows us to efficiently select “the subject with the smallest number among all available subjects” at every step.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Each node and edge is processed once, and each priority queue operation costs \(\log N\)
• Space complexity: \(O(N + M)\)
  • Required for the graph representation and in-degree management

Implementation Notes

• Python’s heapq module is used for the priority queue (it provides a min-heap)

• Input is read all at once using sys.stdin.read() for faster I/O

• The graph is managed with 1-indexed rather than 0-indexed (since subject numbers start from 1)

• When processing each node, decrease the in-degree of nodes reachable via its outgoing edges, and add them to the queue if their in-degree becomes 0

  Source Code

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    
    graph = [[] for _ in range(n+1)]
    in_degree = [0] * (n+1)
    
    index = 2
    for _ in range(m):
        a = int(data[index])
        b = int(data[index+1])
        index += 2
        graph[a].append(b)
        in_degree[b] += 1
    
    heap = []
    for i in range(1, n+1):
        if in_degree[i] == 0:
            heapq.heappush(heap, i)
    
    result = []
    while heap:
        current = heapq.heappop(heap)
        result.append(current)
        
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                heapq.heappush(heap, neighbor)
    
    print(" ".join(map(str, result)))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.