強連結成分分解

すみません。人からライブラリを拝借して一旦終わります。 理解できないですこれ。

// ---------- 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(" "));
    }
}