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 utils::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);
}
}
}
}
}