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

pub mod strongly_connected_components {
    use std::collections::VecDeque;

    pub fn decompose(graph: &Vec<Vec<usize>>) -> Vec<usize> {
        let mut vs = Vec::new();
        let num_v = graph.len();
        let mut cmp = vec![0; num_v];

        let mut reverse_graph = vec![vec![]; num_v];
        for i in 0..num_v {
            for v in &graph[i] {
                reverse_graph[*v].push(i);
            }
        }
        let mut used = vec![false; num_v];

        let mut stack = VecDeque::new();
        let mut added = vec![false; num_v];
        for i in 0..num_v {
            if used[i] {
                continue;
            }
            stack.push_front(i);
            while !stack.is_empty() {
                let v = stack.pop_front().unwrap();
                stack.push_front(v);
                used[v] = true;
                let mut pushed = false;
                for j in (0..graph[v].len()).rev() {
                    let u = graph[v][j];
                    if !used[u] {
                        stack.push_front(u);
                        pushed = true;
                    }
                }
                if !pushed {
                    stack.pop_front();
                    if !added[v] {
                        vs.push(v);
                        added[v] = true;
                    }
                }
            }
        }

        used = vec![false; num_v];
        let mut k = 0;
        vs.reverse();
        for i in &vs {
            let i = *i;
            if used[i] {
                continue;
            }
            stack.push_front(i);
            used[i] = true;
            cmp[i] = k;
            while !stack.is_empty() {
                let v = stack.pop_front().unwrap();
                stack.push_front(v);
                let mut pushed = false;
                for u in &reverse_graph[v] {
                    let u = *u;
                    if used[u] {
                        continue;
                    }
                    used[u] = true;
                    cmp[u] = k;
                    stack.push_front(u);
                    pushed = true;
                }
                if !pushed {
                    stack.pop_front();
                }
            }
            k += 1;
        }

        return cmp;
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use test_helper::TestCaseProducer;

    #[test]
    fn solve_grl_3_c() {
        let mut input = TestCaseProducer::new_from_directory("./assets/GRL_3_C/in/");
        let mut output = TestCaseProducer::new_from_directory("./assets/GRL_3_C/out/");

        while !input.is_empty() {
            let v: usize = input.next();
            let e: usize = input.next();
            let mut graph = vec![vec![]; v];
            for _ in 0..e {
                let s: usize = input.next();
                let t: usize = input.next();
                graph[s].push(t);
            }

            let cmp = strongly_connected_components::decompose(&graph);
            let q: usize = input.next();
            for _ in 0..q {
                let u: usize = input.next();
                let v: usize = input.next();

                let expected = output.next();

                if cmp[u] == cmp[v] {
                    assert_eq!(1, expected);
                } else {
                    assert_eq!(0, expected);
                }
            }
        }
    }
}