ブログ名

競技プログラミングやお歌のお話をする高菜です。

トップ > Low-link と関節点・橋、そして 2-連結成分・2-辺連結成分分解について

Low-link と関節点・橋、そして 2-連結成分・2-辺連結成分分解について

案外この形でまとめている記事が見つからなかったのと、ライブラリの上手な作り方を思いついてしまいまったのとで、執筆意欲です。

他の既存記事

Low-link と関節点・橋、2-辺連結成分分解まではかなり記事があるのですが、 2-連結成分分解はなかなか見つかりませんね…… みなさま low-link 系のおすすめ記事がありましたら、自薦・他薦問わず教えていただけると嬉しいです。

用語の注意

ここでいう 2-連結成分というのは、2-頂点連結成分、あるいは 2-点連結成分などと呼ばれるもののことです。

ソースコードへのリンク (Rust)

github.com

設計の特徴

この設計の一番の特徴は、橋・関節点、2-連結成分・2-辺連結成分分解を前計算せず、聞かるたびに判定や列挙を行う点です。計測をしていないのでどれくらい速い or 遅いのかはわかりませんが、こうすることで一回の DFS ですべてを計算する設計に比べると関心がよく分離できるように思われます。

Low-link について

説明が面倒なので定義を貼ります。

pub struct LowLink {
    g: Vec<Vec<usize>>, // 隣接リストです。未ビルドならば無向グラフ、ビルド済みならば木辺と後退辺のみが入っています。
    sorted: Vec<usize>, // [i]: pre-order で i 番目である頂点の番号
    ord: Vec<usize>,    // [i]: 頂点 i の pre-order における順位
    low: Vec<usize>, // [i]: 頂点 i から木辺を任意回、後退辺を高々１回辿って行ける頂点の pre-order の最小値
    parent: Vec<usize>, // [i]: 頂点 i が根なら i、さもなくの親頂点の番号
    built: bool,     // ビルド済みなら `true`
}

注意点です。

  1. 入力は連結でなくても大丈夫です。
  2. 根のリストは管理せず、代わりに根のリストが根のリストとしてあり得るもののうち辞書順最小であることを保証します。
  3. 関節点や橋、2-連結成分、2-辺連結成分は管理していません。

構築について

面倒なのでコードを貼ります。

ポイントは

  1. 構築時に（下向きの）木辺と後退辺以外を消しておくと後々なにかと便利
  2. pre-order と親だけ先に計算しておけば low-link は後ろから DP できる

といったあたりでしょうか。

impl LowLink {
    pub fn build(&mut self) {
        assert!(!self.built);
        self.built = true;
        let n = self.g.len();
        self.ord.resize(n, !0);
        self.parent.resize(n, !0);

        // Pre-order (`sorted`, `ord`), `parent` の計算
        let mut used = vec![false; n];
        for i in 0..n {
            if !used[i] {
                self.parent[i] = i;
                used[i] = true;
                build(
                    i,
                    i,
                    &mut self.g,
                    &mut self.parent,
                    &mut self.sorted,
                    &mut self.ord,
                    &mut used,
                );
            }
        }

        // Low-link (`low`) の計算
        self.low = self.ord.clone();
        for &x in self.sorted.iter().rev() {
            for &y in &self.g[x] {
                self.low[x] = self.low[x].min(if self.ord[x] < self.ord[y] {
                    self.low[y]
                } else {
                    self.ord[y]
                });
            }
        }
    }
}

fn build(
    x: usize,
    p: usize,
    g: &mut [Vec<usize>],
    parent: &mut [usize],
    sorted: &mut Vec<usize>,
    ord: &mut [usize],
    used: &mut [bool],
) {
    ord[x] = sorted.len();
    sorted.push(x);
    let mut i = 0;
    while i < g[x].len() {
        let y = g[x][i];
        if y == p {
            g[x].swap_remove(i);
            continue;
        } else if replace(&mut used[y], true) {
            if ord[x] < ord[y] {
                g[x].swap_remove(i);
                continue;
            }
        } else {
            parent[y] = x;
            build(y, x, g, parent, sorted, ord, used);
        }
        i += 1;
    }
}

関節点・橋、そして 2-連結成分・2-辺連結成分分解について

簡単のため、pre-order と頂点番号が一致している、すなわちフィールド sorted, ord は恒等置換であるとしておきましょう。また TeX で書きやすくするため、low[x] を L(x) と表します。

また、通常の１回の DFS ですべてを計算する方法と異なり、木辺なのか後退辺なのかをどう判定するのかについて考える必要がありますが、これは実はとても簡単です。無向辺 \lbrace x, y \rbrace について考えたいとしましょう。必要なら x と y を入れ替えることにより、有向辺 (x, y) が逆辺削除済みグラフに入っているとしてよいです。このとき、 (x, y) が木辺である条件は x \lt y、後退辺である条件は x \gt y です。

関節点

頂点 x が関節点である条件は、ご存知の通り x \le L(y) となる（有向）木辺 (x,y) が存在することです。

橋

辺 \lbrace x, y \rbrace が橋である条件は、ご存知の通り \lbrace x, y \rbrace が木辺であり、かつ適宜 x と y を入れ替えることにより x \lt y としたときに、 x \lt L(y) が成り立つことです。

2-連結成分分解

ここが一番むずかしいところですよね。かくいう私もこちらの問題に出会って、「なるほどです low-link ですね、ええ。関節点でスパパパーンと分けて終了です。（ヘラヘラ）」「いえ難しいではありませんか！！！」をしていました。

atcoder.jp

構築時と同じ DFS を再びして、通った辺を片っ端からスタックに入れていき、「2-連結成分から抜けた」（or 根から抜けた）ときにスタックの適切な箇所以降を切り取って答えに入れていけばよいです。（結局もう一回 DFS しないと行けないの微妙と言われてしまうとそうかもです。）

impl LowLink {
    pub fn biconnected_components(&self) -> Vec<Vec<[usize; 2]>> {
        assert!(self.built);
        let n = self.g.len();
        let mut stack = Vec::new();
        let mut cmp = Vec::new();
        for i in (0..n).filter(|&i| self.parent[i] == i) {
            self.__biconnected_components_dfs(i, &mut stack, &mut cmp);
        }
        cmp
    }
    fn __biconnected_components_dfs(
        &self,
        x: usize,
        stack: &mut Vec<[usize; 2]>,
        cmp: &mut Vec<Vec<[usize; 2]>>,
    ) {
        for &y in &self.g[x] {
            stack.push([x, y]);
            if self.ord[x] < self.ord[y] {
                self.__biconnected_components_dfs(y, stack, cmp);
                if self.parent[x] == x || self.ord[x] <= self.low[y] {
                    let mut c = Vec::new();
                    while let Some([u, v]) = stack.pop() {
                        c.push([u, v]);
                        if [u, v] == [x, y] {
                            break;
                        }
                    }
                    cmp.push(c);
                }
            }
        }
    }
}

2-辺連結成分分解

2-連結成分分解と似ていますが、スタックに入れるのが頂点、スタックから掠め取るタイミングが橋を戻るときです。よくある「橋を通らないように DFS」という方針と実質的には大差ないと思います。

impl LowLink {
    pub fn two_edge_components(&self) -> Vec<Vec<usize>> {
        assert!(self.built);
        let n = self.g.len();
        let mut stack = Vec::new();
        let mut cmp = Vec::new();
        for i in (0..n).filter(|&i| self.parent[i] == i) {
            self.__two_edge_components_dfs(i, &mut stack, &mut cmp);
            cmp.push(take(&mut stack));
        }
        cmp
    }
    fn __two_edge_components_dfs(
        &self,
        x: usize,
        stack: &mut Vec<usize>,
        cmp: &mut Vec<Vec<usize>>,
    ) {
        stack.push(x);
        for &y in &self.g[x] {
            if self.ord[x] < self.ord[y] {
                self.__two_edge_components_dfs(y, stack, cmp);
                if self.ord[x] < self.low[y] {
                    let mut c = Vec::new();
                    while let Some(z) = stack.pop() {
                        c.push(z);
                        if z == y {
                            break;
                        }
                    }
                    cmp.push(c);
                }
            }
        }
    }
}