Overview

This problem asks us to find an order to take all courses, given the condition that certain courses must be completed before others can be taken. Among the courses available to take, we must prioritize the one with the smallest number.

Analysis

This problem can be solved using the classic topological sort technique. If we consider each course as a node and the relationship “course \(A\) must be taken before course \(B\)” as a directed edge \(A \rightarrow B\), then we need to arrange all courses according to their prerequisite relationships — this is exactly an application of topological sort.

Furthermore, this is not just an ordinary topological sort — there is the additional constraint that “among the available candidates, we must choose the course with the smallest number.” For example, when there are multiple nodes with in-degree \(0\), we want to select the one with the smallest number, which can be efficiently achieved using a priority queue (heap).

A naive approach (scanning through the list each time to find the smallest node with in-degree 0) would result in \(O(N^2)\) in the worst case, which is too slow for the constraint \(N \leq 2 \times 10^5\). By using a heap, we can efficiently retrieve the minimum value and process everything efficiently.

Algorithm

This problem uses in-degree-based topological sort (Kahn’s algorithm). Specifically, we proceed with the following steps:

1. Prepare an array in_degree to manage the in-degree of each node (the number of prerequisite courses for that course).
2. Build the graph in adjacency list format: record dependency relationships such as course \(A_j \rightarrow B_j\).
3. Initially, add all nodes with in-degree \(0\) (courses with no prerequisites) to a priority queue (heap).
4. Repeat the following until the queue is empty:
   • Extract the node with the smallest number from the queue (this is the next course to take).
   • Remove edges extending from the extracted node (i.e., mark that course as completed).
   • Decrease the in-degree of the destination nodes by \(1\), and if it becomes \(0\), add that node to the queue.
5. The order of extraction is the answer.

In this way, by using a heap, we can efficiently extract “the node with the smallest number among those with in-degree \(0\).”

Example

For instance, if there are 3 courses with the following prerequisites: - Course 1 → Course 2 - Course 1 → Course 3

Then we take course 1 first, and afterwards, among courses 2 and 3, we take the one with the smaller number (course 2) next. The final order is [1, 2, 3].

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Adding to and extracting from the heap occurs \(N\) times, each taking \(O(\log N)\).
  • Each edge is processed exactly once, so edge processing takes \(O(M)\).
• Space complexity: \(O(N + M)\)
  • The adjacency list and in-degree array require \(O(N + M)\).

Implementation Notes

• Since the input is large, sys.stdin.read is used for faster input.

• The heap uses Python’s heapq, which automatically keeps the minimum value at the front.

• When building the graph, don’t forget to update both the adjacency list and the in-degree array simultaneously.

• Output the result using ' '.join(map(str, result)) for fast and concise output.

  Source Code

import heapq
import sys
from collections import defaultdict, deque

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    graph = defaultdict(list)
    in_degree = [0] * (N + 1)
    
    idx = 2
    for _ in range(M):
        a = int(data[idx])
        b = int(data[idx+1])
        graph[a].append(b)
        in_degree[b] += 1
        idx += 2
    
    # 初期化：入次数が0の頂点を優先度付きキューに入れる
    heap = []
    for i in range(1, N+1):
        if in_degree[i] == 0:
            heapq.heappush(heap, i)
    
    result = []
    
    while heap:
        u = heapq.heappop(heap)
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                heapq.heappush(heap, v)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.