leetcode_solutions/
n820_find_eventual_safe_states.rs

1/*
2 * No: 820
3 * Title: Find Eventual Safe States
4 */
5
6use crate::Solution;
7
8impl Solution {
9    pub fn eventual_safe_nodes(graph: Vec<Vec<i32>>) -> Vec<i32> {
10        use std::collections::{HashMap, HashSet, VecDeque};
11
12        let len = graph.len();
13        let mut reverse_graph: HashMap<usize, HashSet<usize>> = HashMap::new();
14        let mut indegrees: Vec<usize> = vec![0; len];
15        let mut queue = VecDeque::<usize>::new();
16        let mut res = vec![];
17
18        // Reverse the graph
19        for (v, us) in graph.iter().enumerate() {
20            indegrees[v as usize] = us.len();
21
22            if indegrees[v as usize] == 0 {
23                queue.push_back(v);
24            }
25
26            for u in us {
27                reverse_graph
28                    .entry(*u as usize)
29                    .or_insert(HashSet::new())
30                    .insert(v);
31            }
32        }
33
34        // Topological sort
35        while !queue.is_empty() {
36            let curr = queue.pop_front().unwrap();
37            res.push(curr as i32);
38
39            if let Some(vs) = reverse_graph.get(&(curr)) {
40                for v in vs {
41                    indegrees[*v] -= 1;
42                    if indegrees[*v] == 0 {
43                        queue.push_back(*v);
44                    }
45                }
46            }
47        }
48
49        res.sort();
50
51        res
52    }
53}
leetcode_solutions/n820_find_eventual_safe_states.rs

leetcode_solutions/
n820_find_eventual_safe_states.rs
