Topological Sort Practice Test: Kahn's Algorithm, DAG DP
A timed topological-sort checkpoint: ten questions on Kahn's algorithm, cycles and DP over a DAG, then the fewest semesters and counting paths in a DAG in C++.
- Course: Competitive Programming study plan
- Module: Topological sort and DAGs
- Kind: Checkpoint — cleared at 70%
- Reading time: 45 min
- Runtime: Clang 18 · C++20
Checkpoint — Topological sort and DAGs is the checkpoint that closes the Topological sort and DAGs module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
A 45-minute timed checkpoint on module 9: topological orders, Kahn's algorithm and its cycle test, and dynamic programming in topological order.
How it works. Ten questions and two programs, in 45 minutes from when you start the timer. 70% on the questions and both programs accepted clears the module.
Before you start, make sure you can answer these from memory:
- When a topological order exists, and how Kahn's algorithm proves it does not.
- What a min-heap instead of a queue changes about the order.
- Why every path into
uis final whenucomes up in topological order. - How longest path, number of paths and fewest semesters each become one relaxation per edge.
The programs are the fewest semesters to finish every course (or -1 on a cycle), and the number of paths from 1 to n in a DAG modulo 10^9 + 7.
Common questions
How do you find the minimum number of semesters to finish all courses?
Run Kahn's algorithm and give every course a level: a course with no prerequisites is level 1, and each edge u → v sets level[v] = max(level[v], level[u] + 1). The answer is the largest level, or -1 when a cycle stops some course from being placed.
How do you count the paths from 1 to n in a DAG?
Set ways[1] = 1 and process the vertices in topological order, adding ways[u] to ways[v] for every edge u → v, modulo 10^9 + 7. Each path is counted once, by its last edge.
Exercises
Fewest semesters
There are n courses 1 to n and m rules a b (course a must be finished in an earlier semester than course b). Any number of courses can be taken in one semester. Print the fewest semesters needed to finish every course, or -1 if it is impossible.
Input: n m, then m lines a b (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5, a ≠ b). Output: one integer.
5 4
1 3
2 3
3 4
2 5prints
3Semester 1: courses 1 and 2; semester 2: 3 and 5; semester 3: 4.
Count the paths
A directed acyclic graph has vertices 1 to n and m edges (no two edges are the same). Print the number of different paths from vertex 1 to vertex n, modulo 10^9 + 7. (With n = 1 there is one path, the empty one.)
Input: n m, then m lines u v (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5). The graph has no cycle. Output: one integer.
5 6
1 2
1 3
2 4
3 4
4 5
2 5prints
3The paths are 1-2-4-5, 1-3-4-5 and 1-2-5.
In this module: Topological sort and DAGs
← Topological sort — Kahn's algorithm and DP on a DAG · Segment trees and Fenwick trees →