Courier Route Check
EasyGraphs
Problem
A courier company serves n depots numbered 0 to n - 1. Each entry [a, b] of edges is a two-way road between depots a and b.
Return true if a parcel can travel from depot source to depot target along the roads, and false otherwise.
Example 1
- Input:
- n = 5, edges = [[0,1],[1,2],[3,4]], source = 0, target = 2
- Output:
- true
0 → 1 → 2 uses two roads.
Example 2
- Input:
- n = 5, edges = [[0,1],[1,2],[3,4]], source = 0, target = 4
- Output:
- false
Depots 3 and 4 form a separate network.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ edges.length ≤ 2 · 10^5
- 0 ≤ a, b, source, target < n
- Roads may repeat; a road may connect a depot to itself.
Hint
Show the first hint
An edge list is hard to walk. What structure lets you list a node's neighbours quickly?
Walkthrough
How to approach it
01Clarify before coding
- Are roads two-way? Yes, the graph is undirected.
- Is source == target allowed? Yes, and the answer is then true.
- Can there be duplicate roads or self-loops? Yes; the visited array makes them harmless.
02Brute force
Keep a set of reached depots and repeatedly scan the full edge list, adding any depot connected to a reached one, until a scan adds nothing.
Cost: Each scan is O(E) and up to O(V) scans may be needed for a long chain: O(V · E), about 2 · 10^10 here.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.