Numbering the chapters
Drafts of a textbook’s chapters sit in a folder under working numbers from 1 to n. Before printing, the chapters must be given book numbers, also from 1 to n, each used once, so that a chapter another relies on stands before it. There are usually many correct numberings. The editor wants the one where the chapter with working number 1 has as small a book number as possible; among those, the one where chapter 2 has as small a number as possible; and so on.
One of the tests is the chapters of this site’s basic course, with working numbers given in alphabetical order of their addresses.
Input
The first line holds n and m (1 ≤ n ≤ 100,000, 0 ≤ m ≤ 200,000). Then m lines a b: chapter a must stand in the book before chapter b (1 ≤ a, b ≤ n, a ≠ b).
Output
n numbers separated by spaces: the book number of chapter 1, of chapter 2, …, of chapter n. If there is no correct numbering, output -1.
Examples
Example 1
3 1 3 1
2 3 1
Example 2
6 5 5 1 5 2 4 2 6 3 2 3
2 4 6 3 1 5
Limits
- Time · Python
- 4000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The most natural approach: numbers in order, and each next book number goes to the chapter with the smallest working number among those that can already be placed. Check on the first example what number chapter 1 gets.
2Hint 2
Chapter 1 wants a small number, but chapter 3 holds it back. For chapter 1 to stand early, chapter 3 must stand earlier still, even at the cost of chapter 2’s number. Greed from the start of the book does not see this. And from the end?
3Hint 3
Which chapter should get the last number n? Of the chapters that nothing is obliged to follow, it pays most to give it to the one with the larger working number.
4The idea
Number from the end. Number n goes to the chapter with the largest working number among those that no unnumbered chapter is obliged to follow. Cross it out and repeat with number n − 1. This is Kahn’s algorithm on the reversed graph, with the queue replaced by a heap with the maximum on top.
5Walkthrough
Why it pays to give the last number to the largest free chapter c. Suppose that in the best numbering L number n went to another free chapter x; then x < c, since c is the largest free one. Rearrange: c gets number n, and all chapters whose number was greater than c’s former number shift down by one. The numbering stays correct: nothing is obliged to follow c, and the order of the others has not changed. All chapters with working numbers less than c got the same number or one less, and x certainly less. So the new numbering is lexicographically smaller than L, and L was not the best. Then the same problem remains for the other chapters and numbers 1 … n − 1.
Why greed from the start does not work. In the first example chapter 3 must stand before chapter 1. Chapters 2 and 3 are free; greed gives number 1 to chapter 2, then 2 to chapter 3, and chapter 1 gets 3: the answer 3 1 2. But the numbering 2 3 1 is better: chapter 1 gets number 2. Greed from the start builds the lexicographically smallest order of chapters, which is a different problem, and on that one it is correct.
Implementation: for each chapter count how many chapters are obliged to stand after it. Chapters with counter 0 go into the heap (in Python, heapq with a minus sign; in Go, container/heap with the comparison reversed). A chapter taken out gets the next number from the end, and the chapters obliged to stand before it have their counters decremented. If not all numbers were handed out, the graph has a cycle: −1.
5+Solution
6Complexity
Each chapter enters and leaves the heap once, each condition is examined once: O((n + m) log n).
7Common mistakes
- Greed from the start of the book. It minimises the order, not the numbers:
wrong.pyfails on the first example. - From the end, but with the smallest chapter. The last number must go to the chapter with the largest working number: small numbers are needed more by small chapters.
- Outputting the order instead of the numbers. The answer is the book number of each chapter in order of working numbers, not a list of chapters in book order.
- A cycle. If fewer than n numbers were handed out, output −1.