Count Paths in DAG
HardGraphDynamic ProgrammingTopological SortMathLinked List
Description
Given a DAG with n nodes (0..n-1) and a list of directed edges, return the number of distinct directed paths from node 0 to node n-1. If the graph contains a cycle, return 0.
Examples
Input:
n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]Output:
2Explanation:
Two paths exist from node 0 to node 3: 0->1->3 and 0->2->3.
Input:
n = 3, edges = [[0,1],[1,2],[2,0]]Output:
0Explanation:
The graph contains a cycle so it is not a DAG; the answer is 0.
Input:
n = 2, edges = [[0,1]]Output:
1Explanation:
There is exactly one direct edge from node 0 to node 1, so the path count is 1.
Constraints
- •
1 ≤ n ≤ 100 - •
0 ≤ edges.length ≤ 1000