A Directed Acyclic Graph (DAG) is a type of graph that has no cycles in it. In other words, if there is a link from node A to node B, there exists no path from B to A (via any nodes).
Determine whether the directed graph given as input is acyclic.
A list of lists of integers representing the links between nodes, where a node is identified by its index in the list.
Standard I/O for decision problems; generally a truthy value for acyclic graphs, and a falsy one for cyclic graphs. Additionally, your program may halt/not halt to indicate truthy and falsy, if you wish.
[[1, 2], [3, 4], , , , , ]
Represents the following graph (where all edges are directed downwards):
0 / \ 1 2 / \ / 3 4 5 | / 6
This example is acyclic, so the result should be truthy.
[[1, 3], , , ]
Represents the following graph:
-----<-----<---- / \ 0 --> 3 --> 1 --> 2 \---->----/
This example is cyclic, so the result should be falsey. (Sorry for my terrible drawing; if this is unclear let me know.)
- No input will ever be invalid; i.e. no node will link to a node that does not exist
- Self loops must be handled (
[]is a cyclic graph)
This is code-golf, so the fewest bytes in each language wins.