強連結成分分解のRustによる実装

説明

AtCoder典型90問の第21問目、Come Back in One Pieceで初めて強連結成分分解について知ったので、自力で実装してみました。

強連結成分分解(Strongly-Connected-Components, SCC)とは、有向グラフにおいてお互いに行き来可能な頂点を一つのグループにまとめるような頂点の分割です。 強連結成分分解は次のようなアルゴリズムで行われます。

1. ある頂点から帰り掛け順DFSによって頂点に番号をつける。これを全ての頂点に番号付けができるまで繰り返す。
2. 全てのエッジを逆向きにする。
3. 1でつけた番号が最も大きい頂点から、逆向きのグラフ上で到達可能な頂点集合を同じグループとみなす。これを全ての頂点を取り尽くすまで繰り返す。

計算量は深さ優先探索なので、です。

実装

Rustによる実装は以下のようになります。実装は強連結成分分解を参考に、DFSを再帰ではなくスタックベースで実装しています。

use proconio::marker::Usize1;
use proconio::*;
use std::collections::VecDeque;

struct SCC {
    g: Vec<Vec<usize>>,
    r_g: Vec<Vec<usize>>,
    post_order: VecDeque<usize>,
    visited: Vec<bool>,
}

impl SCC {
    fn new(nodes: usize, edges: &Vec<(usize, usize)>) -> Self {
        let mut g = vec![vec![]; nodes];
        let mut r_g = vec![vec![]; nodes];
        for edge in edges {
            g[edge.0].push(edge.1);
            r_g[edge.1].push(edge.0);
        }

        Self {
            g,
            r_g,
            post_order: VecDeque::new(),
            visited: vec![false; nodes],
        }
    }

    // 帰り掛け順でノードを記録する
    fn dfs(&mut self, u: usize) {
        let mut stack = vec![u];
        while let Some(v) = stack.pop() {
            if !self.visited[v] {
                // 行き
                self.visited[v] = true;
                stack.push(v);

                for &w in &self.g[v] {
                    if !self.visited[w] {
                        stack.push(w);
                    }
                }
            } else {
                // 帰り
                self.post_order.push_front(v);
            }
        }
    }

    // 各エッジを逆向きにしたグラフ上で到達可能なノード集合を調べる
    fn rdfs(&mut self, u: usize) -> Vec<usize> {
        let mut stack = vec![u];
        let mut scc = Vec::new();
        while let Some(v) = stack.pop() {
            self.visited[v] = true;
            scc.push(v);
            for &u in &self.r_g[v] {
                if !self.visited[u] {
                    stack.push(u);
                }
            }
        }
        scc
    }

    // 強連結成分を求める
    fn build(&mut self) -> Vec<Vec<usize>> {
        for v in 0..self.g.len() {
            if !self.visited[v] {
                self.dfs(v);
            }
        }

        self.visited = vec![false; self.g.len()];
        let mut sccs = Vec::new();
        for i in 0..self.post_order.len() {
            let v = self.post_order[i];
            if !self.visited[v] {
                sccs.push(self.rdfs(v));
            }
        }
        sccs
    }
}

#[fastout]
fn main() {
    input! {
        n: usize, m: usize,
        edges: [(Usize1, Usize1); m],
    }

    let mut scc = SCC::new(n, &edges);
    let sccs = scc.build();
    println!("{:?}", sccs);
}

参考文献

• 強連結成分分解
• 強連結成分分解の意味とアルゴリズム