Find if Path Exists in Graph
Easy · graph traversal
A region has n towns, numbered 0 to n - 1. The list roads holds the roads between them: each entry [a, b] is a road that joins town a and town b, and you can drive along it in either direction.
You start in town source and want to reach town destination, driving along roads and passing through other towns if you need to.
Return true if you can get from source to destination, and false otherwise. If the two are the same town, the answer is true, even when there are no roads at all.
No road joins a town to itself, and no pair of towns is listed twice.
Examples
Example 1
Input: n = 4, roads = [[0, 1], [1, 2], [2, 3]], source = 0, destination = 3
Output: true
Drive 0 to 1, then 1 to 2, then 2 to 3.
Example 2
Input: n = 5, roads = [[0, 1], [1, 2], [3, 4]], source = 0, destination = 4
Output: false
Towns 0, 1 and 2 are linked to each other, and so are 3 and 4, but no road crosses between the two sets.
Example 3
Input: n = 1, roads = [], source = 0, destination = 0
Output: true
You are already there.
Constraints
- 1 <= n <= 2000
- 0 <= len(roads) <= 10^4
- Each road holds two different town numbers in the range 0 to n - 1.
- No pair of towns appears more than once.
- 0 <= source, destination <= n - 1