強連結成分分解
すみません。人からライブラリを拝借して一旦終わります。 理解できないですこれ。
// ---------- begin scc ---------- pub fn strongly_connected_components<G, I>(size: usize, graph: G) -> (usize, Vec<usize>) where G: Fn(usize) -> I, I: Iterator<Item = usize>, { let mut ord = vec![0; size]; let mut res = vec![0; size]; let mut vertex = vec![]; let mut dfs = vec![]; let mut id = 0; for s in 0..size { if ord[s] > 0 { continue; } vertex.push(s); ord[s] = vertex.len(); dfs.push((s, graph(s))); while let Some((v, mut it)) = dfs.pop() { (|| { while let Some(u) = it.next() { if ord[u] == 0 { vertex.push(u); ord[u] = vertex.len(); dfs.push((v, it)); dfs.push((u, graph(u))); return; } } let low = graph(v).map(|u| ord[u]).min().unwrap_or(ord[v]); if low < ord[v] { ord[v] = low; return; } while let Some(u) = vertex.pop() { ord[u] = !0; res[u] = id; if u == v { break; } } id += 1; })(); } } res.iter_mut().for_each(|p| *p = id - 1 - *p); (id, res) } // ---------- end scc ---------- // ---------- begin CSR ---------- pub struct CSR { size: usize, pos: Vec<u32>, elist: Vec<u32>, } impl CSR { pub fn new<I>(size: usize, it: I) -> Self where I: Iterator<Item = (usize, usize)> + Clone, { let mut pos = vec![0; size + 1]; for (s, t) in it.clone() { assert!(s < size && t < size); pos[s + 1] += 1; } for i in 1..=size { pos[i] += pos[i - 1]; } let mut x = pos[..size].to_vec(); let mut elist = vec![0; pos[size] as usize]; for (s, t) in it { let x = &mut x[s]; elist[*x as usize] = t as u32; *x += 1; } CSR { size, pos, elist } } pub fn list(&self, v: usize) -> impl Iterator<Item = usize> + '_ { assert!(v < self.size); let s = self.pos[v] as usize; let t = self.pos[v + 1] as usize; self.elist[s..t].iter().map(|p| *p as usize) } } // ---------- end CSR ----------
使用例
fn main() { input! { n: usize, m: usize, e: [(u32, u32); m], } let graph = CSR::new(n, e.iter().map(|e| (e.0 as usize, e.1 as usize))); let (len, id) = strongly_connected_components(n, |v| graph.list(v)); let csr = CSR::new(n, id.iter().enumerate().map(|(v, k)| (*k, v))); println!("{}", len); for i in 0..len { let len = csr.list(i).count(); println!("{} {}", len, csr.list(i).join(" ")); } }