A dependency graph has n items forming a directed acyclic graph, where an edge u v means u must come before v. A dependency chain is a directed path a1 -> a2 -> ... -> ak. Find the maximum number of nodes k on any such chain. A single node by itself counts as a chain of length 1.
Line 1: two integers n and m — the number of nodes (labeled 0 through n-1) and the number of directed edges.
Each of the next m lines: two integers u v, a directed edge from u to v (read as: u must come before v).
It is guaranteed the graph is acyclic, with no self-loops and no duplicate edges.
A single integer: the maximum number of nodes on any directed path.
Example 1
Input
4 3 0 1 1 2 0 2
Expected
3
Explanation
The longest chain is 0 -> 1 -> 2, which has 3 nodes. Node 3 is isolated and does not extend it.
Example 2
Input
3 0
Expected
1
Explanation
With no edges the longest chain is a single node, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →