SCC

[tipstar0125]

参考：https://qiita.com/AkariLuminous/items/a2c789cebdd098dcb503

[tipstar0125]

#[derive(Debug, Clone)]
struct StronglyConnectedComponent<'a> {
    size: usize,
    edge: &'a Vec<Vec<usize>>,
    visited: Vec<bool>,
    order: Vec<usize>,
    low: Vec<usize>,
    ids: Vec<usize>,
    group_size: usize,
}

impl<'a> StronglyConnectedComponent<'a> {
    fn new(edge: &'a Vec<Vec<usize>>) -> Self {
        let size = edge.len();
        let visited = vec![false; size];
        let order = vec![0; size];
        let low = vec![0; size];
        let ids = vec![0; size];

        StronglyConnectedComponent {
            size,
            edge,
            visited,
            order,
            low,
            ids,
            group_size: 0,
        }
    }
    fn build(&mut self) {
        let mut cnt = 0;
        let mut stack = vec![];
        for i in 0..self.size {
            if !self.visited[i] {
                self.dfs(i, &mut cnt, &mut stack);
            }
        }
        for i in 0..self.size {
            self.ids[i] = self.group_size - 1 - self.ids[i];
        }
    }
    fn dfs(&mut self, v: usize, cnt: &mut usize, stack: &mut Vec<usize>) {
        self.visited[v] = true;
        self.order[v] = *cnt;
        self.low[v] = self.order[v];
        stack.push(v);
        *cnt += 1;
        for &next in &self.edge[v] {
            if !self.visited[next] {
                self.dfs(next, cnt, stack);
                self.low[v] = self.low[v].min(self.low[next]);
            } else {
                self.low[v] = self.low[v].min(self.order[next]);
            }
        }
        if self.order[v] == self.low[v] {
            while let Some(u) = stack.pop() {
                self.order[u] = self.size;
                self.ids[u] = self.group_size;
                if v == u {
                    break;
                }
            }
            self.group_size += 1;
        }
    }
    fn scc(&mut self) -> Vec<Vec<usize>> {
        self.build();
        let mut groups = vec![vec![]; self.group_size];
        for i in 0..self.size {
            groups[self.ids[i]].push(i);
        }
        groups
    }
}

[tipstar0125]

ライブラリチェック：https://atcoder.jp/contests/practice2/tasks/practice2_g 提出：https://atcoder.jp/contests/practice2/submissions/47563283