779. Count All Paths in Directed Graph (0 to N-1)

Given a directed acyclic graph (DAG) with n nodes (numbered 0 to n-1) and a list of directed edges, count the number of distinct SIMPLE paths from node 0 to node n-1. A simple path visits each node at most once. If n == 1, there is exactly one trivial path. If no path exists, return 0. Input is a JSON object with fields n (int) and edges (list of [u, v] pairs).

Input: A JSON object: {"n": N, "edges": [[u,v],...]}.

Output: Return an integer — the number of distinct simple paths.

Examples

Input: {"n":4,"edges":[[0,1],[0,2],[1,3],[2,3]]}
Output: 2
Explanation: Two paths: 0->1->3 and 0->2->3.

Input: {"n":2,"edges":[[0,1]]}
Output: 1
Explanation: Single edge.

Input: {"n":3,"edges":[]}
Output: 0
Explanation: No edges, no path from 0 to 2.

Constraints

• 1 <= n <= 8
• 0 <= edges.length <= 20
• edges[i] = [u, v] with 0 <= u, v < n

Asked by