We’re preparing your current view and syncing the latest data.
Given an undirected graph with n nodes labeled from 0 to n-1 and an array edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi, determine if there exists a valid path between two given nodes source and destination.
The input consists of an integer n, an array edges where each element is a pair of integers representing edges between nodes, and two integers source and destination.
Return true if there is a path from source to destination, otherwise return false.
1 <= n <= 2 * 10^4 0 <= edges.length <= 2 * 10^4 edges[i].length == 2 0 <= ai, bi <= n - 1 0 <= source, destination <= n - 1
Example 1
Input
n = 3, edges = [[0, 1], [1, 2], [2, 0]], source = 0, destination = 2
Output
true
Explanation
There is a path from node 0 to node 2 via node 1 or directly as there is a cycle.
Example 2
Input
n = 6, edges = [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], source = 0, destination = 5
Output
false
Explanation
There is no path connecting the components containing 0 and 5.