Does the One-Way Network Contain a Circuit
Implement hasCircuit
You are given a network of one-way roads as an adjacency list of a directed graph. Decide whether it contains a circuit: a route that follows the roads and comes back to the node it started from (a road from a node to itself also counts).
In a directed graph, meeting an already visited node is not enough to prove a circuit; the important thing is whether that node is still on the current search path.
Example 1:
Input: graph = [[1,4],[2],[3],[1],[5],[]]
Output: true
Example 2:
Input: graph = [[1,2],[2],[]]
Output: false
Example 3:
Input: graph = [[0]]
Output: true
+ 15 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 10 nodes numbered 0 … n-1; graph[u] lists, in increasing order, every node v that has a one-way road u → v (adjacency-list form of a directed graph) - ●
There are no repeated roads; a road from a node to itself is allowed and counts as a circuit - ●
The graph may be disconnected - ●
A circuit is a route that follows the one-way roads and returns to the node it started from; return true if the graph contains one
graph =
[[1,4], [2], [3], [1], [5], []]