Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@NokonoKotlin(おこ ていゆ)

強連結成分分解 : コード例付き

Last updated at Posted at 2024-11-30

まえがき

この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。 (この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)

強連結成分とは

有向グラフの例

SCC.001.jpeg

有向グラフ $G$ の頂点集合の部分集合で、以下を満たす集合 $S$ を強連結成分 ( SCC ) といいます。

  • $S$ に属する任意の $2$ 頂点間は有向辺を辿って移動可能である。
  • $S$ に属する任意の頂点と、$S$ に属さない任意の頂点との間は、高々一方向にのみ移動可能である。

SCC.002.jpeg

$G$ の強連結成分は複数種類存在し、それらの集合はいずれも互いに素です。$G$ の強連結成分分解では、$G$ の頂点がどの強連結成分に属するかを特定し、また、強連結成分同士の関係をグラフとして構築します。

頂点 $x$ が属する強連結成分を $c_x$ とします。有向グラフ $G$ において、辺 $(u \rightarrow v)$ の端点 $u,v$ がそれぞれ相異なる強連結成分 $c_u,c_v$ に属しているなら、それら $2$ つの強連結成分の関係を辺 $(c_u \rightarrow c_v)$ で表現します。

SCC.003.jpeg

強連結成分同士の関係によって構築される有効グラフを $Gs$ とすると、$Gs$ は多重辺を持つ DAG (平路を持たない有向グラフ) になります。ただし、今回は多重辺をマージして $1$ つの辺として扱うことにします。辺に重みがついている場合は重みをどうマージするのかも考慮する必要があります。

$Gs$ は DAG なので、頂点をトポロジカルソートすることができます。$Gs$ の頂点、すなわち各強連結成分には頂点番号が割り振られますが、これから紹介する強連結成分分解アルゴリズムでは、それらの番号の割り当てがトポロジカルソートの結果の $1$ つになります。

SCC.004.jpeg


アルゴリズム

アルゴリズムは $2$ つのステップからなります。

ステップ 1

未到達の頂点が存在しなくなるまで、以下の操作を繰り返します。

  • 未到達の頂点のうちいずれかを任意に DFS の始点として選び、到達済みの頂点に入らない枝刈り付きの DFS を行う。

SCC.005.jpeg

ここで、ステップ $1$ の DFS を通して、これ以上移動不可能であることが判明するタイミングが早い順に、頂点に数値 ($\mathrm{goback\_ time}$) を $0$ から割り当てていきます。


ステップ 1 の様子

頂点 $x$ からこれ以上移動不可能であることが判明するとは、頂点 $x$ から出る辺を調べ終わったタイミングのことです。

SCC.006.jpeg

$\mathrm{goback\_ time}$ が小さいほど、移動不可能であることが判明するタイミングが早いことを表します。

SCC.007.jpeg

これ以上探索できなくなったら、未到達の頂点から新たに頂点を選び、そこから改めて DFS と $\mathrm{goback\_ time}$ の割り当てを行います。

SCC.008.jpeg

この時、ステップ $1$ においてすでに訪れた頂点はいずれも到達済みとして枝刈りします。

SCC.009.jpeg

複数の辺が出ている頂点は、それら全てが移動不可能と判明したタイミングで $\mathrm{goback\_ time}$ に数値を割り当てます。

SCC.010.jpeg

残りの未到達頂点についても、同様に DFS を行ってください。

SCC.011.jpeg

始点にする未到達頂点を探す操作は、頂点 $0$ から到達済み頂点をスキップしながらイテレートしていけば良いです。


ステップ 2

このステップでは、$G$ の辺の始点と終点を入れ替えた辺 (逆辺) で構成されるグラフ $rG$ を考えます。

SCC.012.jpeg

未到達の頂点が存在しなくなるまで、以下の操作を繰り返します。

  • 未到達の頂点のうち、$\mathrm{goback\_ time}$ が最大のものを DFS の始点として選び、ステップ $2$ において到達済みの頂点に入らない枝刈り付きの DFS を、グラフ $rG$ 上で行う。

強連結成分の構築

頂点 $S$ を始点とする $rG$ 上の DFS で (ステップ $2$ において) 初めて到達できた頂点は $S$ と同じ強連結成分に属します。そうでない頂点は、$S$ と異なる強連結成分に属します。このことは後で証明します。つまり、ステップ $2$ における DFS を一回行うと、強連結成分を $1$ つ構築できます。

また、ステップ $2$ のイテレートにおいて、$i$ 番目 (0-index) の DFS によって構築される強連結成分には、強連結成分同士の関係を表す有向グラフ $gs$ における頂点番号として $i$ を割り当てておきます。


辺の構築

頂点 $S$ を始点とする DFS の途中で現在実行中の DFS より前 (かつステップ $2$) の DFS で到達済みの頂点に到達できた場合、その頂点を $y$ とすると、強連結成分同士の関係を表す有向グラフ $Gs$ において、頂点 $y$ が属する強連結成分 $c_y$ から、現在構築中の強連結成分 $c_S$ への辺が存在します。よって、このタイミングで $Gs$ の有向辺 $(c_y \rightarrow c_S)$ を構築できます。なお、実際の処理ではこの時点で強連結成分 $c_S$ の番号が判明しています。

またアルゴリズムの手続を考えると、辺の構築を行う時点で、頂点 $y$ が属する強連結成分 $c_y$ をすでに特定できていることが保証されています。ステップ $2$ では逆辺を考えているので、強連結成分の構築がちゃんとできているなら、ここでの辺の構築の正当性は自明です。


ステップ 2 の様子

DFS で初めて到達した頂点で強連結成分を構築します。以下の図は 0-index で $0$ 番目の DFS の結果なので、強連結成分には番号 $0$ を割り当て、$\mathrm{SCC}_0$ とします。

なお、実用上は強連結成分のデータを構造体などで集約して管理しておくと良いでしょう。頂点重みのマージや、属する頂点の集合もこの構造体で管理すると便利です。

SCC.013.jpeg

このイテレートではステップ $2$ において到達済みの頂点をスキップし、未到達の頂点のうち $\mathrm{goback\_ time}$ が最大の頂点を始点として改めて DFS を続けます。

SCC.014.jpeg

$i$ 回目の DFS で、すでに構築した強連結成分 $\mathrm{SCC}_x$ 内の頂点に到達できる場合、強連結成分同士の関係を表す有向グラフ $Gs$ における辺 $(\mathrm{SCC}_x \rightarrow \mathrm{SCC}_i)$ $(x \leq i)$ を構築します。

SCC.015.jpeg

このように $\mathrm{SCC}$ および $Gs$ を構築すると、$\mathrm{SCC}$ に割り振られた番号は $Gs$ におけるトポロジカルソートの結果の $1$ つになります (トポロジカルソートの結果は一意ではないことに注意) 。


強連結成分の構築手続きの正当性

一

ステップ $2$ の DFS で、始点 $S$ から頂点 $x$ に初めて到達した場合、$S$ と $x$ が同じ強連結成分に属することを証明します。

ステップ $2$ の DFS は逆辺によるグラフ $rG$ 上で行うので、$S$ から $x$ に到達可能ということから、元のグラフ $G$ 上で頂点 $x$ から頂点 $S$ へのパスが存在することがわかります。また、ステップ $2$ の手続きより、頂点 $S$ の $\mathrm{goback\_ time}$ に割り当てられた数値は、頂点 $x$ の $\mathrm{goback\_ time}$ に割り当てられた数値よりも大きいことがわかります。

ここで、元のグラフ $G$ 上で頂点 $S$ から頂点 $x$ へのパスが存在しない、すなわち $G$ 上で頂点 $x$ から頂点 $S$ 方向に一方通行であると仮定して、背理法による証明を行います。

元のグラフ $G$ 上に頂点 $x$ から頂点 $S$ へのパスが存在することは先述の通りなので、頂点 $x$ の $\mathrm{goback\_ time}$ は、仮定が成り立つならば必ず頂点 $S$ の $\mathrm{goback\_ time}$ よりも後に数値が割り振られることになり、頂点 $S$ の $\mathrm{goback\_ time}$ に割り当てられた数値は、頂点 $x$ の $\mathrm{goback\_ time}$ に割り当てられた数値よりも小さくなります。これは事実と異なるので、仮定は成り立たないことがわかります。

よって、元のグラフでは $S$ から $x$、$x$ から $S$ の双方向にパスが存在します。これは $S$ と $x$ が同じ強連結成分に属する条件を満たします。

二

(DFS での到達済みか未到達かは関係なく) グラフ $rG$ 上で $S$ からのパスが存在しない頂点 $x$ について、$S$ と $x$ が同じ強連結成分に属さないことを証明します。このとき、元のグラフ $G$ 上に $x$ から $S$ へのパスが存在しないので、$S$ と $x$ は強連結成分である条件を満たしません。

三

ステップ $2$ において、ある頂点 $x$ が、始点 $S$ からの DFS の開始前の時点で到達済み場合、頂点 $x$ はそれよりも前に $S$ でないある始点 $t$ からの DFS によって初めて到達済みの状態になったことがわかります。

$t$ から $x$ に初めて到達しているので、$t$ と $x$ は同じ強連結成分に属することがわかります。ここで、ステップ $2$ の手続きより、頂点 $S$ は、$S$ を始点とする DFS よりも前に到達済みになった頂点のいずれからも到達できないことが保証されているので、$t$ と $S$ は同じ強連結成分には含まれません。よって、$S$ と $x$ は異なる強連結成分に属します。

まとめ

以上 $3$ つより、ステップ $2$ における強連結成分の構築の正当性を示すことができました。


強連結成分への番号割り当てがトポロジカルソート結果になることの証明

ステップ $2$ の手続きより、$\mathrm{SCC}_i$ に入る辺の始点の強連結成分はいずれも番号が $i$ より小さいことが保証されています。強連結成分の関係を表すグラフは DAG なので、強連結成分 $\mathrm{SCC}_x$ から $\mathrm{SCC}_y$ に到達可能ならば $x \leq y$ となっていることが保証されています。

ソースコード

使い方は後述します。あとコメントの英語が拙いのは気にしないでください。雰囲気がわかればいいのです。

ライセンスは守ってくださいね (このライブラリの冒頭に以下を書くだけで良いです)。

ライセンスに従わない利用を確認した場合、ライセンスに従わない利用をやめるよう指示するなどの処置を取る場合があります。

#include<iostream>
#include<stack>
#include<vector>
#include<cassert>
using namespace std;



/*
    このコメントは消さないでください。
    Don't Remove this Comment !!

    Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024.
    Released under the MIT license(https://opensource.org/licenses/mit-license.php)
*/
template<typename type_Nodeweight , typename type_Edgeweight>
class SCC_decomposition{
    inline static const int UNDEFINED_Symbol = -2;
    inline static const int UNREACHED_Symbol = -1;

    public:
    struct Edge{
        int from, to; 
        type_Edgeweight weight;
        int id;
        Edge(int f,int t,type_Edgeweight w):from(f),to(t),weight(w){}
    };

    struct _SCC{
        private:
        vector<int> members;
        bool edgew_f = false;
        int id_;
        bool built = false;

        public:
        type_Nodeweight node_w_sum , node_w_max , node_w_min;

        type_Edgeweight edge_w_sum , edge_w_max , edge_w_min;

        _SCC(int c_id) : id_(c_id){}

        int size() const& {
            return this->members.size();
        }

        int id() const& {
            return this->id_;
        }

        int operator[](int i) const& {
            assert(0 <= i && i < this->size());
            return members[i];
        }

        void add_node(int x , type_Nodeweight w){
            assert(built == false);
            if(members.size() == 0){
                node_w_sum = w;
                node_w_min = w;
                node_w_max = w;
            }else{
                node_w_sum = w + node_w_sum;
                node_w_min = min(w , node_w_min);
                node_w_max = max(w , node_w_max);
            }
            members.push_back(x);
        }
        
        void add_edge(type_Edgeweight w){
            assert(built == false);

            if(edgew_f == false){
                edge_w_sum = w;
                edge_w_min = w;
                edge_w_max = w;
                edgew_f = true;
            }else{
                edge_w_sum = w + edge_w_sum;
                edge_w_min = min(w , edge_w_min);
                edge_w_max = max(w , edge_w_max);
            }
        }

        void close(){
            assert(built == false);
            built = true;
        }
    };


    private:

    int m_V;
    vector<vector<Edge>> m_G;
    vector<vector<Edge>> m_rG;
    vector<type_Nodeweight> NodeWeight;
    vector<int> m_SCC_Number; 
    vector<_SCC> m_SCC;
    vector<vector<int>> m_SCC_G;
    vector<int> m_depth;
    vector<int> m_level;


    public:
    SCC_decomposition(){}
    SCC_decomposition(int V_) : m_V(V_){
        m_G = vector<vector<Edge>>(m_V);
        m_rG = vector<vector<Edge>>(m_V);
        NodeWeight = vector<type_Edgeweight>(m_V,0);
    }


    void set_nodeweight(int x , type_Nodeweight w){
        assert(0 <= x && x < m_V);
        NodeWeight[x] = w;
    }

    void add_edge(int u , int v , type_Edgeweight w = type_Edgeweight(1)){
        assert(0 <= u && u < m_V && 0 <= v && v < m_V);
        m_G[u].emplace_back(u,v,w);
        m_rG[v].emplace_back(v,u,w);
    }

    void build(){
        vector<int>(m_V,UNREACHED_Symbol).swap(m_SCC_Number);
        m_SCC.clear();
        m_SCC_G.clear();
        m_depth.clear();
        m_level.clear();

        vector<bool> visited(m_V,false);
        vector<int> index(m_V,0);
        vector<int> before(m_V , UNDEFINED_Symbol);

        vector<int> goback_time(m_V,UNREACHED_Symbol);
        int goback_counter = 0;

        for(int x = 0 ; x < m_V ; x++){
            if(visited[x])continue;

            int now = x;
            int nxt = UNDEFINED_Symbol;
            
            while(true){
                if(now == UNDEFINED_Symbol)break;
                visited[now] = true;

                if(index[now] < m_G[now].size()){
                    nxt = m_G[now][index[now]].to;
                    index[now]++;
                    if(nxt != before[now] && visited[nxt] == 0){
                        before[nxt] = now; 
                        now = nxt;
                    }
                }else{
                    goback_time[now] = goback_counter++;
                    if(before[now] != UNDEFINED_Symbol){
                        now = before[now];
                    }else{
                        break;
                    }
                }
            }     
        }

        vector<int> bucket(m_V,UNDEFINED_Symbol);
        for(int x = 0 ; x < m_V ; x++)bucket[goback_time[x]] = x;

        int SCC_number_counter = 0;
        vector<int> edge_origin_counter(m_V,UNDEFINED_Symbol);

        for(int t = m_V - 1 ; t >= 0 ; t--){
            int x = bucket[t];
            if(m_SCC_Number[x] != UNREACHED_Symbol)continue;

            stack<int> st;
            st.push(x);
            int depth_ = 0;
            m_SCC_Number[x] = SCC_number_counter;
            _SCC component(SCC_number_counter);

            while(!st.empty()){
                int now = st.top();
                st.pop();
                assert(m_SCC_Number[now] == SCC_number_counter);
                component.add_node(now , NodeWeight[now]);
                for(Edge e : m_rG[now]){
                    if(m_SCC_Number[x] == UNREACHED_Symbol || m_SCC_Number[e.to] == component.id())component.add_edge(e.weight);
                    if(m_SCC_Number[e.to] != UNREACHED_Symbol){
                        if( m_SCC_Number[e.to] != component.id() && edge_origin_counter[m_SCC_Number[e.to]] != SCC_number_counter){
                            edge_origin_counter[m_SCC_Number[e.to]] = SCC_number_counter;
                            m_SCC_G[m_SCC_Number[e.to]].push_back(SCC_number_counter);
                            depth_ = max(m_depth[m_SCC_Number[e.to]]+1 , depth_);
                        }
                        continue;
                    }
                    st.push(e.to);
                    m_SCC_Number[e.to] = SCC_number_counter;
                }
            }
            component.close();
            m_SCC.push_back(component);
            m_SCC_G.emplace_back();
            m_depth.push_back(depth_);
            SCC_number_counter++;
        }
        
        vector<int>(this->sccd_size(),UNREACHED_Symbol).swap(m_level);
        for( int c = this->sccd_size() - 1 ; c >= 0 ; c-- ){
            m_level[c] = 0;
            for( int nx : (*this)[c] )m_level[c] = max(m_level[c] , m_level[nx]+1);
        }
    }

    int graph_size(){
        return m_V;
    }

    int sccd_size(){
        return m_SCC.size();
    }

    const _SCC& SCC_of_Node(int x){
        assert(0 <= x && x < this->graph_size());
        return m_SCC[m_SCC_Number[x]];
    }

    const _SCC& SCC_of_Number(int c){
        assert(0 <= c && c < this->sccd_size());
        return m_SCC[c];
    }

    int depth(int c){
        assert(0 <= c && c < this->sccd_size());
        return m_depth[c];
    }

    int level(int c){
        assert(0 <= c && c < this->sccd_size());
        return m_level[c];
    }

    const vector<int>& operator[](int c){
        assert(0 <= c && c < this->sccd_size());
        return m_SCC_G[c];
    }
};

使い方

有向グラフの強連結成分(SCC)のデータと、それらの関係を管理する。

  • 概要

    • Static な使用を想定しているが、O(V+E) 時間でデータの再構築をできるように設計してある。
    • それぞれの強連結成分(SCC)には番号が割り振られる。
    • _SCC 構造体に、強連結成分内の頂点や辺のデータを保存する。
    • SCC の関係をグラフで表現する際、多重辺の情報を保存せず、辺重みのない隣接リストで表現する。
      • 1 つの SCC を 1 つの頂点に対応づけた隣接リストを構築する。
      • SCC の関係のグラフは DAG になる。
    • それぞれの SCC に割り振られる番号は、SCC の関係のグラフにおけるトポロジカルソート順の 1 つである。
      • 0 から始まり、数値の大小がトポロジカルソートにおける順序を表す

  • _SCC 構造体について

    • 強連結成分のデータをもつ。
      • id() := SCC の番号
      • size() := SCC に属する頂点の個数
      • [i] := SCC に属する頂点のうち、管理されている順(無意味な順序)で i 番目の頂点番号
    • SCC に属する頂点や辺について、それらの重みの集約 (Sum,Min,Max) などを管理する。
      • モノイドなら乗る。カスタマイズ性を上げるために、ブラックボックスにはしていない。
      • node_w_sum , node_w_max , node_w_min := 順に頂点重みの 総和、最大値、最小値
      • edge_w_sum , edge_w_max , edge_w_min := 順に辺重みの 総和、最大値、最小値

  • インターフェース (構築)

    • add_edge(u,v,w) := 重み w の有向辺 (u→v) を追加
    • set_nodeweight(x,w) := 頂点 x の頂点重みを w としてセットする。
    • build() := O(V+E) 時間でデータ構築

  • インターフェース (取得) : build() によって構築したデータに対する操作

    • graph_size() := 元のグラフのサイズ
    • sccd_size() := SCC の関係を表すのグラフのサイズ (強連結成分の個数)
    • SCC_of_Node(x) := 頂点 x が属する強連結成分のデータを、_SCC 構造体の const 参照で返す。
    • SCC_of_Number(c) := 番号が c の強連結成分のデータを、_SCC 構造体の const 参照で返す。
    • depth(c) := 強連結成分の関係のグラフで、番号が c の SCC !!! に到達可能 !!! な SCC のうち、最遠のものまでのパス長
    • level(c) := 強連結成分の関係のグラフで、番号が c の SCC !!! から到達可能 !!! な SCC のうち、最遠のものまでのパス長
    • [c] := SCC の関係のグラフにおいて、番号が c の SCC から辺 1 本で移動可能な SCC の隣接リスト (const 参照)

  • 仕様,注意点

    • SCC 内部の辺重みの集約をとるので多重辺を許さない。(集約したいモノイドに応じた方法で)あらかじめ多重辺をマージしておく。
    • 本質とは関係ないですが、ある辺の逆辺と言った時、元の辺の始点と終点を入れ替えただけで、重みなどの他の要素はそのままのものを指す。
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?