1014. Check if a Directed Graph is a DAG

Given a directed graph with n nodes and a list of directed edges, determine whether it is a DAG (directed acyclic graph) — i.e. it contains no directed cycle. Return true or false. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Boolean — true or false.

Examples

Input: {"n":3,"edges":[[0,1],[1,2]]}
Output: true
Explanation: No cycle.

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]]}
Output: false
Explanation: A directed cycle exists.

Input: {"n":1,"edges":[]}
Output: true
Explanation: Single node.

Constraints

• 1<=n<=10^5
• directed

Asked by