674. Is There a Way
A city has n junctions numbered 0 to n-1. The list edges describes two-way roads: edges[i] = [u, v] means you can drive from u to v and from v to u. A courier starts at junction source and wants to reach junction destination.
Return true if there is some sequence of roads leading from source to destination, otherwise false. A junction is always reachable from itself, so the answer is true when the two are equal. The road list may contain duplicate roads and roads that start and end at the same junction. Aim for O(n + m) time and space.
Example 1
- Input:
- n = 6edges = [[0,1],[1,3],[4,5]]source = 0destination = 3
- Output:
- true
- Explanation:
Driving 0 to 1 to 3 uses two roads, so junction 3 is reachable.
Example 2
- Input:
- n = 6edges = [[0,1],[1,3],[4,5]]source = 0destination = 5
- Output:
- false
- Explanation:
Junctions 4 and 5 are only connected to each other, so 5 cannot be reached from 0.
Constraints
1 ≤ n ≤ 200000
0 ≤ edges.length ≤ 200000
0 ≤ u, v, source, destination < n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)