1971. Find if Path Exists in Graph

There is a bi-directional graph with `n` vertices, where each vertex is labeled from `0` to `n - 1` (inclusive). The edges in the graph are represented as a 2D integer array `edges`, where each `edges[i] = [ui, vi]` denotes a bi-directional edge between vertex `ui` and vertex `vi`. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex `start` to vertex `end`.

Given `edges` and the integers `n`, `start`, and `end`, return `true` if there is a valid path from `start` to `end`, or `false` otherwise.

Example 1:

```Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2
```

Example 2:

```Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
```

Constraints:

• `1 <= n <= 2 * 105`
• `0 <= edges.length <= 2 * 105`
• `edges[i].length == 2`
• `0 <= ui, vi <= n - 1`
• `ui != vi`
• `0 <= start, end <= n - 1`
• There are no duplicate edges.
• There are no self edges.

1971. Find if Path Exists in Graph
``````struct Solution;

use rustgym_util::UnionFind;

impl Solution {
fn valid_path(n: i32, edges: Vec<Vec<i32>>, start: i32, end: i32) -> bool {
let n = n as usize;
let mut uf = UnionFind::new(n);
for e in edges {
let u = e[0] as usize;
let v = e[1] as usize;
uf.union(u, v);
}
let start = start as usize;
let end = end as usize;
uf.find(start) == uf.find(end)
}
}

#[test]
fn test() {
let n = 3;
let edges = vec_vec_i32![[0, 1], [1, 2], [2, 0]];
let start = 0;
let end = 2;
let res = true;
assert_eq!(Solution::valid_path(n, edges, start, end), res);
let n = 6;
let edges = vec_vec_i32![[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]];
let start = 0;
let end = 5;
let res = false;
assert_eq!(Solution::valid_path(n, edges, start, end), res);
}
``````