Overview

Given \(N\) tasks with prerequisite (dependency) conditions, the problem asks to find the lexicographically smallest execution order among all orders that satisfy every prerequisite. This is an application of topological sorting.

Analysis

Essence of the Problem: Topological Sort

The relation “Task \(A_i\) must come before Task \(B_i\)” can be represented as a directed edge \(A_i \to B_i\) in a directed graph. Finding an order that satisfies all prerequisites is exactly a topological sort of this graph.

When a Cycle Exists

If the directed graph contains a cycle, for example “Task 1 → Task 2 → Task 3 → Task 1”, a circular dependency occurs and none of these tasks can be executed first. In this case, output -1.

How to Achieve Lexicographically Smallest Order?

In a standard topological sort (BFS-based Kahn’s algorithm), nodes with in-degree 0 (tasks whose all prerequisites have been satisfied) are dequeued and processed.

If we replace this queue with a min-heap (priority queue), we can always select “the task with the smallest number among all executable tasks,” yielding the lexicographically smallest order.

For example, with \(N=4\) and prerequisites “3→1” and “3→2”: 1. Tasks with in-degree 0: {3, 4} → choose the smallest: 3 2. After completing task 3, in-degree 0: {1, 2, 4} → choose the smallest: 1 3. Remaining: {2, 4} → choose 2 4. Remaining: {4} → choose 4 5. Result: 3 1 2 4

Algorithm

We extend Kahn’s algorithm (BFS-based topological sort) with a heap.

1. Build the graph: Store each edge \(A_i \to B_i\) in an adjacency list and compute the in-degree (indegree) of each node.
2. Initialization: Add all nodes with in-degree 0 to a min-heap.
3. Loop: Repeat the following until the heap is empty:
   • Extract the smallest node \(u\) from the heap and append it to the result sequence.
   • For each node \(v\) reachable via an outgoing edge from \(u\), decrease \(v\)’s in-degree by 1.
   • If \(v\)’s in-degree becomes 0, add it to the heap.
4. 判定 (Verdict): If the length of the result sequence is \(N\), output it. If it is less than \(N\), a cycle exists, so output -1.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Each node is inserted into and removed from the heap at most once (\(O(N \log N)\))
  • Each edge is traversed once (\(O(M)\); if heap operations occur during edge processing, it becomes \(O(M \log N)\))
• Space complexity: \(O(N + M)\)
  • Total for the adjacency list, in-degree array, heap, and result array

Implementation Notes

• Using a min-heap: Python’s heapq is a min-heap by default, so it can be used directly to extract tasks with the smallest number first.

• Cycle detection: If the number of nodes processed by the topological sort is less than \(N\), a cycle exists. There is no need to perform separate cycle detection using DFS or other methods.

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

  Source Code

import heapq
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    indegree = [0] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        indegree[b] += 1
    
    heap = []
    for i in range(1, N + 1):
        if indegree[i] == 0:
            heapq.heappush(heap, i)
    
    result = []
    while heap:
        u = heapq.heappop(heap)
        result.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                heapq.heappush(heap, v)
    
    if len(result) == N:
        print(*result)
    else:
        print(-1)

main()

---

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