Description#
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 source
to vertex destination
.
Given edges
and the integers n
, source
, and destination
, return true
if there is a valid path from source
to destination
, or false
otherwise.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/1971.Find%20if%20Path%20Exists%20in%20Graph/images/validpath-ex1.png)
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2
Example 2:
![](https://spcdn.pages.dev/leetcode/problems/1971.Find%20if%20Path%20Exists%20in%20Graph/images/validpath-ex2.png)
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 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 <= source, destination <= n - 1
- There are no duplicate edges.
- There are no self edges.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def validPath(
self, n: int, edges: List[List[int]], source: int, destination: int
) -> bool:
def dfs(i):
if i == destination:
return True
vis.add(i)
for j in g[i]:
if j not in vis and dfs(j):
return True
return False
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
vis = set()
return dfs(source)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
private boolean[] vis;
private List<Integer>[] g;
public boolean validPath(int n, int[][] edges, int source, int destination) {
vis = new boolean[n];
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (var e : edges) {
int a = e[0], b = e[1];
g[a].add(b);
g[b].add(a);
}
return dfs(source, destination);
}
private boolean dfs(int source, int destination) {
if (source == destination) {
return true;
}
vis[source] = true;
for (int nxt : g[source]) {
if (!vis[nxt] && dfs(nxt, destination)) {
return true;
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
vector<bool> vis(n);
vector<vector<int>> g(n);
for (auto& e : edges) {
int a = e[0], b = e[1];
g[a].emplace_back(b);
g[b].emplace_back(a);
}
function<bool(int)> dfs = [&](int i) -> bool {
if (i == destination) return true;
vis[i] = true;
for (int& j : g[i]) {
if (!vis[j] && dfs(j)) {
return true;
}
}
return false;
};
return dfs(source);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func validPath(n int, edges [][]int, source int, destination int) bool {
vis := make([]bool, n)
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
var dfs func(int) bool
dfs = func(i int) bool {
if i == destination {
return true
}
vis[i] = true
for _, j := range g[i] {
if !vis[j] && dfs(j) {
return true
}
}
return false
}
return dfs(source)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| impl Solution {
pub fn valid_path(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
let mut disjoint_set: Vec<i32> = vec![0; n as usize];
// Initialize the set
for i in 0..n {
disjoint_set[i as usize] = i;
}
// Traverse the edges
for p_vec in &edges {
let parent_one = Solution::find(p_vec[0], &mut disjoint_set);
let parent_two = Solution::find(p_vec[1], &mut disjoint_set);
disjoint_set[parent_one as usize] = parent_two;
}
let p_s = Solution::find(source, &mut disjoint_set);
let p_d = Solution::find(destination, &mut disjoint_set);
p_s == p_d
}
pub fn find(x: i32, d_set: &mut Vec<i32>) -> i32 {
if d_set[x as usize] != x {
d_set[x as usize] = Solution::find(d_set[x as usize], d_set);
}
d_set[x as usize]
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def validPath(
self, n: int, edges: List[List[int]], source: int, destination: int
) -> bool:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(n))
for u, v in edges:
p[find(u)] = find(v)
return find(source) == find(destination)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
private int[] p;
public boolean validPath(int n, int[][] edges, int source, int destination) {
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
for (int[] e : edges) {
p[find(e[0])] = find(e[1]);
}
return find(source) == find(destination);
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
vector<int> p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) -> int {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
};
for (auto& e : edges) p[find(e[0])] = find(e[1]);
return find(source) == find(destination);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func validPath(n int, edges [][]int, source int, destination int) bool {
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, e := range edges {
p[find(e[0])] = find(e[1])
}
return find(source) == find(destination)
}
|