Checkpoint: The Longest Chain
Challenge on lesson: Checkpoint — The Order Is the Algorithm
CHALLENGE
Difficulty: advanced+25 XP
**Task.** A directed graph with n nodes and m edges (given as pairs u v, meaning an edge u → v). The graph is guaranteed acyclic. Print the number of edges on the longest directed path (a path visits distinct nodes following edge directions). **Constraints:** 1 ≤ n ≤ 200000; 1 ≤ m ≤ 400000. Recursion depth can hit 200000 — an explicit order (Kahn) or iterative DFS is required. **Budget check:** one topological sort plus one DP sweep: O(n + m).
Press Submit to check your solution.
Back to lesson: Checkpoint — The Order Is the Algorithm