Overview

This is a problem of performing a topological sort on a DAG (Directed Acyclic Graph) where, while satisfying prerequisite relationships, we prioritize selecting the “course with the smallest number.”

Analysis

Essence of the Problem

Prerequisite relationships between courses can be represented as directed edges \(A \to B\), meaning “course \(A\) must be completed before course \(B\) can be taken.” This is exactly the structure of a Directed Acyclic Graph (DAG), and arranging all courses in an order consistent with the prerequisites corresponds to a topological sort.

Difference from Standard Topological Sort

In a general topological sort, multiple valid orderings can exist. However, in this problem, there is an additional condition: “among the courses available to take, always choose the one with the smallest number.”

For example, with \(N=3\) and no prerequisites, possible topological sorts include \((1,2,3)\), \((2,1,3)\), \((3,2,1)\), and many others. But under this problem’s rule of always choosing the smallest-numbered course, the answer is uniquely determined as \((1, 2, 3)\).

Issues with a Naive Approach

If we exhaustively search all “available courses” at each step to find the minimum number, each step takes \(O(N)\), resulting in \(O(N^2)\) overall. For \(N = 2 \times 10^5\), this risks TLE.

Solution

By managing the set of available courses with a min-heap (priority queue), we can extract the smallest number in \(O(\log N)\).

Algorithm

The following is the procedure for topological sort using a priority queue (lexicographically smallest order):

1. Compute in-degrees: For each course, determine the number of prerequisites (= in-degree \(\text{in\_degree}[v]\)).
2. Initialization: Add all courses with in-degree \(0\) (no prerequisites) to the min-heap.
3. Iterative processing:
   • Extract the course \(u\) with the smallest number from the heap and record it in the course order.
   • For every course \(v\) that has an edge from \(u\), decrement \(\text{in\_degree}[v]\) by \(1\).
   • If \(\text{in\_degree}[v]\) becomes \(0\), add \(v\) to the heap.
4. Repeat until the heap is empty.

Concrete example: \(N=4\), prerequisites: \(1 \to 3\), \(2 \to 3\), \(3 \to 4\)

• Initial: Courses with in-degree \(0\) are \(1, 2\) → Heap: \(\{1, 2\}\)
• Extract \(1\) → In-degree of course \(3\) changes from \(2 \to 1\) → Heap: \(\{2\}\)
• Extract \(2\) → In-degree of course \(3\) changes from \(1 \to 0\) → Heap: \(\{3\}\)
• Extract \(3\) → In-degree of course \(4\) changes from \(1 \to 0\) → Heap: \(\{4\}\)
• Extract \(4\) → Done. Answer: \(1\ 2\ 3\ 4\)

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Each course is added to and removed from the heap at most once, with each operation taking \(O(\log N)\). Edge processing totals \(O(M)\).
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the adjacency list, and at most \(O(N)\) for the heap.

Implementation Notes

• Using a min-heap: Python’s heapq is a min-heap by default, so it can be used directly to prioritize extracting the smallest-numbered course.

• Fast input: Since \(N, M\) can be up to \(2 \times 10^5\), we use sys.stdin.buffer.read() for bulk reading to speed up input.

• 1-indexed arrays: Since course numbers start from \(1\), we set the array size to \(N+1\) so that indices can be used directly.

  Source Code

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    in_degree = [0] * (N + 1)
    adj = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        adj[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:
        u = heapq.heappop(heap)
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                heapq.heappush(heap, v)
    
    print(' '.join(map(str, result)))

main()

---

This editorial was generated by claude4.6opus-thinking.