Given the edges
of a directed graph where edges[i] = [ai, bi]
indicates there is an edge between nodes ai
and bi
, and two nodes source
and destination
of this graph, determine whether or not all paths starting from source
eventually, end at destination
, that is:
source
node to the destination
nodesource
node to a node with no outgoing edges, then that node is equal to destination
.source
to destination
is a finite number.Return true
if and only if all roads from source
lead to destination
.
Example 1:
Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2 Output: false Explanation: It is possible to reach and get stuck on both node 1 and node 2.
Example 2:
Input: n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3 Output: false Explanation: We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.
Example 3:
Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3 Output: true
Example 4:
Input: n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2 Output: false Explanation: All paths from the source node end at the destination node, but there are an infinite number of paths, such as 0-1-2, 0-1-1-2, 0-1-1-1-2, 0-1-1-1-1-2, and so on.
Example 5:
Input: n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1 Output: false Explanation: There is infinite self-loop at destination node.
Constraints:
1 <= n <= 104
0 <= edges.length <= 104
edges.length == 2
0 <= ai, bi <= n - 1
0 <= source <= n - 1
0 <= destination <= n - 1
struct Solution;
impl Solution {
fn leads_to_destination(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
let n = n as usize;
let s = source as usize;
let d = destination as usize;
let mut visited: Vec<bool> = vec![false; n];
let mut graph: Vec<Vec<usize>> = vec![vec![]; n];
for edge in edges {
let u = edge[0] as usize;
let v = edge[1] as usize;
graph[u].push(v);
}
if !graph[d].is_empty() {
return false;
}
Self::dfs(s, &mut visited, &graph, d)
}
fn dfs(u: usize, visited: &mut [bool], graph: &[Vec<usize>], d: usize) -> bool {
if u == d {
true
} else {
if visited[u] {
false
} else {
visited[u] = true;
let mut count = 0;
for &v in &graph[u] {
if !Self::dfs(v, visited, graph, d) {
return false;
} else {
count += 1;
}
}
visited[u] = false;
count != 0
}
}
}
}
#[test]
fn test() {
let n = 3;
let edges = vec_vec_i32![[0, 1], [0, 2]];
let source = 0;
let destination = 2;
let res = false;
assert_eq!(
Solution::leads_to_destination(n, edges, source, destination),
res
);
let n = 4;
let edges = vec_vec_i32![[0, 1], [0, 3], [1, 2], [2, 1]];
let source = 0;
let destination = 3;
let res = false;
assert_eq!(
Solution::leads_to_destination(n, edges, source, destination),
res
);
let n = 4;
let edges = vec_vec_i32![[0, 1], [0, 2], [1, 3], [2, 3]];
let source = 0;
let destination = 3;
let res = true;
assert_eq!(
Solution::leads_to_destination(n, edges, source, destination),
res
);
let n = 3;
let edges = vec_vec_i32![[0, 1], [1, 1], [1, 2]];
let source = 0;
let destination = 2;
let res = false;
assert_eq!(
Solution::leads_to_destination(n, edges, source, destination),
res
);
let n = 2;
let edges = vec_vec_i32![[0, 1], [1, 1]];
let source = 0;
let destination = 1;
let res = false;
assert_eq!(
Solution::leads_to_destination(n, edges, source, destination),
res
);
let n = 4;
let edges = vec_vec_i32![[0, 1], [0, 2], [1, 3], [2, 3], [1, 2]];
let source = 0;
let destination = 3;
let res = true;
assert_eq!(
Solution::leads_to_destination(n, edges, source, destination),
res
);
}