Reachability Between Two Graph Vertices
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
An undirected graph has vertices `0` through `n-1`, no self-edges and no duplicate edges. Return whether there is a path from `source` to `destination`. If both labels are the same, the zero-edge path is valid.
```cpp
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source, int destination);
};
```
### Examples
**Example 1:**
```text
n = 4, edges = [[0,1],[1,3]], source = 0, destination = 3
Output: true
Explanation: The path is 0->1->3.
```
**Example 2:**
```text
n = 3, edges = [], source = 0, destination = 2
Output: false
Explanation: The isolated vertices are not connected.
```
### Constraints
- `1 <= n <= 2 * 10^5`; `0 <= edges.length <= 2 * 10^5`.
- Edge endpoints, source and destination lie in `[0,n-1]`.
- No self-edges or duplicate edges.
### Clarifying Questions
Edges can be traversed in either direction. Vertex labels do not describe connectivity.
```hint Inspect the structure
Which vertices can a queue reach when initialized only with source?
```
### Reasoning checkpoints
- Recognize exactly the vertices connected to the source, including isolated vertices and equal source/destination labels.
- Handle cycles and disconnected components within the stated graph size.
### Optional extensions
How could you preprocess the fixed graph to answer many later connectivity queries?
Overview: Reachability Between Two Graph Vertices. An undirected graph has vertices 0 through n-1, no self-edges, and at most one edge for each vertex pair. Return whether source and destination are joined by a path. The path may have zero edges when both vertices are the same.
