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:
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:
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 * 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ui, vi <= n - 1ui != vi0 <= 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)
}
|
