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:
- At least one path exists from the
sourcenode to thedestinationnode - If a path exists from the
sourcenode to a node with no outgoing edges, then that node is equal todestination. - The number of possible paths from
sourcetodestinationis 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 <= 1040 <= edges.length <= 104edges.length == 20 <= ai, bi <= n - 10 <= source <= n - 10 <= destination <= n - 1- The given graph may have self-loops and parallel edges.
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
);
}