Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

強連結成分分解

強連結成分分解(Strongly-Connected-Components, SCC)をメモっておきます。

強連結成分というのは、有向グラフにおいて、そのグループに含まれている点は、どの点u,vをとってもお互いに行き来出来るというものです。例えばサイクルなどは明らかに強連結成分ですし、孤立点のない無向グラフなども当然そうなります。

与えられた有向グラフを強連結成分に分解すると、便利なことがあります。例えば、それぞれの強連結成分を一つのノードとして潰してしまえば、サイクルが消えて、単なるDAGと見れたりします。

SCCは、

  1. どこかの点からDFSしてポストオーダー(帰りがけ)で番号をつける。こうすると、葉に近い方に小さい番号がつく
  2. すべてのエッジを逆向きにする
  3. 番号が一番大きい点からDFSして、到達出来るものを同じグループとみなす

というアルゴリズムで求めることが出来ます。このようにポストオーダーに番号をつけることが有効なケースは結構ありますね。

pub struct SCC<'a> {
    g: &'a [Vec<usize>],
    r_g: Vec<Vec<usize>>,
    post_order: VecDeque<usize>,
    used: Vec<bool>,
    pub order: Vec<usize>,
}

impl <'a> SCC<'a> {
    pub fn new(g: &'a [Vec<usize>]) -> Self {
        let n = g.len();
        let mut r_g = vec![vec![]; n];
        for u in 0..n {
            let conn = &g[u];
            for &v in conn {
                r_g[v].push(u);
            }
        }
        Self {
            g,
            r_g,
            post_order: VecDeque::new(),
            used: vec![false; n],
            order: vec![n; n],
        }
    }
    fn dfs(&mut self, u: usize) {
        self.used[u] = true;
        for i in 0 .. self.g[u].len() {
            let v = self.g[u][i];
            if !self.used[v] {
                self.dfs(v);
            }
        }
        self.post_order.push_front(u);
    }
    fn rdfs(&mut self, u: usize, k: usize) {
        self.used[u] = true;
        self.order[u] = k;
        for i in 0 .. self.r_g[u].len() {
            let v = self.r_g[u][i];
            if !self.used[v] {
                self.rdfs(v, k);
            }
        }
    }
    pub fn build(&mut self) {
        for v in 0 .. self.g.len() {
            if !self.used[v] {
                self.dfs(v);
            }
        }
        // dbg!(&self.post_order);
        self.used = vec![false; self.g.len()];
        let mut k = 0;
        for i in 0 .. self.post_order.len() {
            let v = self.post_order[i];
            if !self.used[v] {
                self.rdfs(v, k);
                k += 1;
            }
        }
    }
}