Follow the Arrows
A directed graph is given as an adjacency list arrows: arrows[i] lists the nodes that node i has an arrow to. Nodes are numbered 0 to len(arrows) - 1. An arrow can only be walked from its tail i to its head, never backwards.
Return true if there is a walk from start to target that follows zero or more arrows in their direction, and false otherwise. If start == target the answer is true. A node may have an arrow to itself, and a list may name the same node more than once.
Example 1
arrows [[1],[2],[],[0]]
start 0
target 2
returns true
The walk 0 to 1 to 2 follows two arrows.
Example 2
arrows [[1],[2],[],[0]]
start 2
target 0
returns false
From node 2 there is no arrow out at all, so node 0 cannot be reached.
Constraints
1 <= len(arrows) <= 500 <= arrows[i][j] < len(arrows)- At most 100 arrows in total
0 <= start, target < len(arrows)
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Forms a TreeEasy
- Groups After Each MergeEasy
- Largest CrowdEasy
- Loop in the WiringEasy
- Mutual FollowsEasy
- Paint BucketEasy
- Pointer Loop LengthEasy
- Rumour DaysEasy