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