aboutsummaryrefslogtreecommitdiff
path: root/other/all_path_src_target.rs
diff options
context:
space:
mode:
Diffstat (limited to 'other/all_path_src_target.rs')
-rw-r--r--other/all_path_src_target.rs54
1 files changed, 0 insertions, 54 deletions
diff --git a/other/all_path_src_target.rs b/other/all_path_src_target.rs
deleted file mode 100644
index c406cd8..0000000
--- a/other/all_path_src_target.rs
+++ /dev/null
@@ -1,54 +0,0 @@
-use std::collections::VecDeque;
-struct Solution;
-
-impl Solution {
- pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
- let (src, dst, mut rev) = (0, (graph.len() - 1) as i32, vec![0; graph.len()]);
- for (u, adj) in graph.iter().enumerate() {
- for &v in adj {
- rev[v as usize] += 1;
- }
- }
- let mut top_sort_q = VecDeque::new();
- for v in 0..graph.len() {
- if rev[v] == 0 {
- top_sort_q.push_back(v as i32);
- }
- }
- let mut ans = vec![vec![]; graph.len()];
- while let Some(v) = top_sort_q.pop_front() {
- if v == src {
- ans[src as usize].push(vec![src])
- }
- if v == dst {
- break;
- }
- for &next in graph[v as usize].iter() {
- let (ans_v, ans_next) = {
- if v < next {
- let (ans_left, ans_right) = ans.split_at_mut(v as usize + 1);
- (&ans_left[v as usize], &mut ans_right[(next - v - 1) as usize])
- } else {
- let (ans_left, ans_right) = ans.split_at_mut(next as usize + 1);
- (&ans_right[(v - next - 1) as usize], &mut ans_left[next as usize])
- }
- };
- for path in ans_v {
- let mut new_path = path.clone();
- new_path.push(next);
- ans_next.push(new_path);
- }
- rev[next as usize] -= 1;
- if rev[next as usize] == 0 {
- top_sort_q.push_back(next);
- }
- }
- }
- std::mem::take(&mut ans[dst as usize])
- }
-}
-
-fn main() {
- let graph = vec![vec![1,2],vec![3],vec![3],vec![]];
- print!("{:?}", Solution::all_paths_source_target(graph));
-}