653. Find if Path Exists in Graph
You have an undirected graph with n vertices labeled 0 through n - 1. Its wiring is given as a list edges, where each entry [u, v] is a two-way connection between vertices u and v. The graph is not necessarily connected, and the edge list may contain repeated edges or self-loops.
Write a function that receives n, edges, and two vertices source and destination, and returns true if some walk along the edges leads from source to destination, and false otherwise. Every vertex is considered reachable from itself, so when source == destination the answer is always true.
Example 1:
Input: n = 5, edges = [[0,1],[1,2],[2,0],[3,4]], source = 0, destination = 2
Output: true
Explanation: Vertices 0, 1, 2 form a triangle, so 0 can reach 2 directly (or via 1). Vertices 3 and 4 sit in a separate component, but that doesn't matter for this query.
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,0],[3,4]], source = 0, destination = 4
Output: false
Explanation: Same graph, different query: vertex 4 lives in the {3, 4} component, and no edge bridges it to the triangle containing 0.
Constraints:
- 1 ≤ n ≤ 2 * 10⁵
- 0 ≤ edges.length ≤ 2 * 10⁵
- 0 ≤ u, v ≤ n - 1
- 0 ≤ source, destination ≤ n - 1
- The edge list may contain self-loops and duplicate edges.
Hints:
Rephrase the question: are source and destination in the same connected component?
Traversal answers it: build an adjacency list, then BFS or DFS outward from source, marking vertices as visited. If destination is ever marked, the answer is true.
Union-Find answers it without traversing: union the two endpoints of every edge, then compare find(source) with find(destination).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 5, edges = [[0,1],[1,2],[2,0],[3,4]], source = 0, destination = 2
Expected output: true