aboutsummaryrefslogtreecommitdiff
path: root/other/min_time_apples_tree.rs
diff options
context:
space:
mode:
Diffstat (limited to 'other/min_time_apples_tree.rs')
-rw-r--r--other/min_time_apples_tree.rs47
1 files changed, 47 insertions, 0 deletions
diff --git a/other/min_time_apples_tree.rs b/other/min_time_apples_tree.rs
new file mode 100644
index 0000000..537e5cc
--- /dev/null
+++ b/other/min_time_apples_tree.rs
@@ -0,0 +1,47 @@
+use std::collections::HashSet;
+struct Solution;
+
+impl Solution {
+ pub fn min_time(n: i32, edges: Vec<Vec<i32>>, has_apple: Vec<bool>) -> i32 {
+ let mut adj_list: Vec<Vec<i32>> = vec![vec![]; n as usize];
+ for e in edges {
+ adj_list[e[0] as usize].push(e[1]);
+ adj_list[e[1] as usize].push(e[0]);
+ }
+ let mut total = 0i32;
+ let mut vis: HashSet<i32> = HashSet::new();
+ Self::dfs(0, adj_list, &mut vis, has_apple, &mut total);
+ total
+ }
+ fn dfs(node: i32, adj_list: Vec<Vec<i32>>, vis: &mut HashSet<i32>,
+ has_apple: Vec<bool>, total: &mut i32) -> bool {
+ let mut res = false;
+ if has_apple[node as usize] {
+ res = true;
+ }
+ vis.insert(node);
+ for i in &adj_list[node as usize] {
+ if !vis.contains(&i) {
+ if Self::dfs(*i, adj_list, vis, has_apple, total) {
+ *total += 2;
+ res = true;
+ }
+ }
+ }
+ res
+ }
+}
+
+fn main() {
+ let edges = vec![
+ vec![0,1], vec![0,2],
+ vec![1,4], vec![1,5],
+ vec![2,3], vec![2,6]
+ ];
+ let has_apple1 = vec![false,false,true,false,true,true,false];
+ let has_apple2 = vec![false,false,true,false,false,true,false];
+ let has_apple3 = vec![false,false,false,false,false,false,false];
+ println!("{}", Solution::min_time(7, edges, has_apple1)); //expect: 8
+ println!("{}", Solution::min_time(7, edges, has_apple2)); //expect: 6
+ println!("{}", Solution::min_time(7, edges, has_apple3)); //expect: 0
+}