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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

use std::collections::HashSet;

#[derive(Debug, Eq, PartialEq)]
struct Node {
    id: usize,
    discovery: usize,
    lowest: usize,
    on_stack: bool,
}

impl Node {
    pub fn new(id: usize) -> Self {
        let discovery = std::usize::MAX;
        let lowest = std::usize::MAX;
        let on_stack = false;
        Node {
            id,
            discovery,
            lowest,
            on_stack,
        }
    }

    fn visit(&mut self, time: usize) {
        self.discovery = time;
    }

    fn is_visited(&self) -> bool {
        self.discovery != std::usize::MAX
    }
}

#[derive(Debug, Eq, PartialEq)]
pub enum EdgeKind {
    TreeEdge,
    BackEdge,
    CrossEdge,
    ForwardEdge,
}

#[derive(Debug, Eq, PartialEq)]
pub struct Edge {
    pub tail: usize,
    pub head: usize,
    pub kind: EdgeKind,
}

impl Edge {
    fn new(tail: usize, head: usize, kind: EdgeKind) -> Self {
        Edge { tail, head, kind }
    }
}

#[derive(Debug, Eq, PartialEq)]
pub struct Graph {
    pub n: usize,
    pub edges: Vec<Edge>,
    adj: Vec<HashSet<usize>>,
    nodes: Vec<Node>,
    stack: Vec<usize>,
    time: usize,
}

impl Graph {
    pub fn new(n: usize) -> Self {
        let time = 0;
        let adj = vec![HashSet::new(); n];
        let nodes = (0..n).map(Node::new).collect();
        let edges = vec![];
        let stack = vec![];
        Graph {
            n,
            time,
            adj,
            nodes,
            edges,
            stack,
        }
    }

    pub fn init_with_edges(&mut self, edges: Vec<Vec<i32>>, directed: bool) {
        for edge in edges {
            let u = edge[0] as usize;
            let v = edge[1] as usize;
            if !directed {
                self.adj[u].insert(v);
                self.adj[v].insert(u);
            } else {
                self.adj[u].insert(v);
            }
        }
    }

    pub fn dfs(&mut self, u: usize, parent: usize) {
        self.nodes[u].visit(self.time);
        self.time += 1;
        let neighbours: Vec<usize> = self.adj[u].iter().copied().collect();
        for v in neighbours {
            if v == parent {
                continue;
            }
            if !self.nodes[v].is_visited() {
                self.edges.push(Edge::new(u, v, EdgeKind::TreeEdge));
                self.dfs(v, u);
            } else {
                self.edges.push(Edge::new(u, v, EdgeKind::BackEdge));
            }
        }
    }

    pub fn travase(&mut self) {
        for u in 0..self.n {
            if !self.nodes[u].is_visited() {
                self.dfs(u, u);
            }
        }
    }
}