Does the Road Network Contain a Loop
Implement hasLoop
You are given the road network of a region as an adjacency list of an undirected graph. Decide whether there is a loop: a closed route through at least three towns that does not use the same road twice.
A depth-first search that remembers where it came from finds a loop the moment it meets an already visited town by a different road.
Example 1:
Input: graph = [[1],[0,2,3],[1,3],[1,2],[5],[4],[]]
Output: true
Example 2:
Input: graph = [[1],[0,2],[1]]
Output: false
Example 3:
Input: graph = [[1],[0],[3],[2]]
Output: false
+ 14 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 10 nodes numbered 0 … n-1; graph[u] lists, in increasing order, every neighbour of u (adjacency-list form of an undirected graph) - ●
If v is in graph[u] then u is in graph[v]; there are no self-loops and no repeated edges - ●
The graph may be disconnected - ●
A loop is a path that starts and ends at the same node, uses at least 3 nodes and never repeats an edge; return true if the graph contains one
graph =
[[1], [0,2,3], [1,3], [1,2], [5], [4], []]