887. Longest DAG Route
A railway company runs one-way freight lines between n stations numbered 0 to n - 1. Each entry edges[i] = [from, to] is a line that can only be travelled from from to to. The company guarantees the network has no directed cycle, though several lines may connect the same pair of stations.
A freight train may begin at any station and may stop at any station. Return the greatest number of lines it can travel in one trip. If there are no lines at all the answer is 0.
Example 1
- Input:
- n = 6, edges = [[0,1],[1,2],[0,3],[3,4],[4,2],[2,5]]
- Output:
- 4
- Explanation:
The route 0 - 3 - 4 - 2 - 5 uses 4 roads, longer than 0 - 1 - 2 - 5 which uses 3.
Example 2
- Input:
- n = 4, edges = [[3,1],[3,2]]
- Output:
- 1
- Explanation:
Station 3 can only reach 1 or 2 directly and neither leads anywhere, so the longest route is a single road.
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ edges.length ≤ 2 * 105
- 0 ≤ from, to < n and from ≠ to; the graph is acyclic (parallel edges allowed)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)