Skip to main content

rustgym/leetcode/
_802_find_eventual_safe_states.rs

1struct Solution;
2
3impl Solution {
4    fn eventual_safe_nodes(graph: Vec<Vec<i32>>) -> Vec<i32> {
5        let n = graph.len();
6        let mut res = vec![];
7        let mut state = vec![0; n];
8        for i in 0..n {
9            if Self::dfs(i, &mut state, &graph) {
10                res.push(i as i32);
11            }
12        }
13        res
14    }
15
16    fn dfs(u: usize, state: &mut [i32], graph: &[Vec<i32>]) -> bool {
17        match state[u] {
18            3 => false,
19            2 => true,
20            1 => {
21                state[u] = 3;
22                false
23            }
24            _ => {
25                state[u] = 1;
26                let mut s = 2;
27                for &v in &graph[u] {
28                    if !Self::dfs(v as usize, state, graph) {
29                        s = 3;
30                    }
31                }
32                state[u] = s;
33                state[u] == 2
34            }
35        }
36    }
37}
38
39#[test]
40fn test() {
41    let graph = vec_vec_i32![[1, 2], [2, 3], [5], [0], [5], [], []];
42    let res = vec![2, 4, 5, 6];
43    assert_eq!(Solution::eventual_safe_nodes(graph), res);
44}