1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

//! 有向图的环检测
use std::slice::Iter;

use super::Digraph;
/// 有向图环检测
///
/// # 用法
///```
/// use algorithms_fourth::digraph::Digraph;

/// use algorithms_fourth::digraph::cycle::DirectedCycler;
///
///        let mut g = Digraph::new(6);
///        g.add_edge(0, 5);
///        g.add_edge(3, 5);
///        g.add_edge(4, 3);
///        g.add_edge(5, 4);
///        let dc = DirectedCycler::new(&g);
///        assert_eq!(dc.has_cycle(),true);
///        assert_eq!(dc.cycle().collect::<Vec<_>>(),vec![&3,&4,&5,&3]);
/// ```
pub struct DirectedCycler {
    marked: Vec<bool>,
    edge_to: Vec<usize>,
    cycle: Vec<usize>,
    on_stack: Vec<bool>,
}
impl DirectedCycler {
    pub fn new(g: &Digraph) -> Self {
        let on_stack = vec![false; g.vertex_count()];
        let marked = vec![false; g.vertex_count()];
        let edge_to = vec![usize::MAX; g.vertex_count()];
        let mut dc = DirectedCycler {
            marked,
            edge_to,
            cycle: Vec::new(),
            on_stack,
        };
        for v in 0..g.vertex_count() {
            if !dc.marked[v] {
                dc.dfs(g, v);
            }
        }
        dc
    }

    fn dfs(&mut self, g: &Digraph, v: usize) {
        self.on_stack[v] = true;
        self.marked[v] = true;
        for w in g.adj(v) {
            if self.has_cycle() {
                return;
            } else if !self.marked[*w] {
                self.edge_to[*w] = v;
                self.dfs(g, *w);
            } else if self.on_stack[*w] {
                let mut x = v;
                while x != *w {
                    if x == usize::MAX {
                        panic!("error:{:?} v:{},w:{}", self.cycle(), v, w)
                    }
                    self.cycle.push(x);
                    x = self.edge_to[x];
                }
                self.cycle.push(*w);
                self.cycle.push(v);
            }
        }
        self.on_stack[v] = false;
    }

    pub fn has_cycle(&self) -> bool {
        !self.cycle.is_empty()
    }
    pub fn cycle(&self) -> Iter<usize> {
        self.cycle.iter()
    }
}
#[cfg(test)]
mod test {
    use crate::digraph::Digraph;

    use super::DirectedCycler;

    #[test]
    fn test() {
        let mut g = Digraph::new(6);
        g.add_edge(0, 5);
        g.add_edge(3, 5);
        g.add_edge(4, 3);
        g.add_edge(5, 4);
        let dc = DirectedCycler::new(&g);
        assert_eq!(dc.has_cycle(), true);
        assert_eq!(dc.cycle().collect::<Vec<_>>(), vec![&3, &4, &5, &3]);
    }
}