Jump Game on Graph

Can you reach the last node of a directed graph by jumping along edges?

graphs bfs reachability directed simulation

You are given a directed graph with nodes numbered 0 through n-1. You start at node 0. From a node u, you can jump to any node v for which there is a directed edge (u, v). Your goal is to reach node n-1. Return True if it is possible, otherwise False.

Implement the function `can_reach(n: int, edges: list[list[int]]) -> bool` where n is the number of nodes and edges is a list of [u, v] pairs representing directed edges. You may assume the graph is simple (no self-loops, no duplicate edges) and that 1 <= n <= 1000 and 0 <= len(edges) <= 5000. The graph may not be connected. You should traverse the graph efficiently, avoiding revisiting nodes.

Note: The function must be named exactly `can_reach` and take the arguments in the order shown.

Constraints

1 <= n <= 1000
0 <= len(edges) <= 5000
Each edge is [u, v] with 0 <= u, v < n and u != v.
No duplicate edges.
Your solution should run in O(n + len(edges)) time and O(n + len(edges)) space.

Example

>>> can_reach(5, [[0,1],[1,2],[2,3],[3,4]])
True
>>> can_reach(5, [[0,1],[2,3],[3,4]])
False
>>> can_reach(3, [[0,2]])
True
>>> can_reach(1, [])
True

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build an adjacency list where adj[u] contains all nodes v such that (u,v) is an edge.

Use a queue (or stack) to explore all reachable nodes starting from 0.

Keep a visited set or boolean array to avoid cycles and redundant work.

If node n-1 is discovered during traversal, you can return True early.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.