Strongly Connected Components - 強連結成分分解
(Library/Graph/StronglyConnectedComponents.hpp)

View this file on GitHub
Last update: 2026-02-13 15:23:31+09:00
Include: #include "Library/Graph/StronglyConnectedComponents.hpp"

Strongly Connected Components - 強連結成分分解

頂点数 $V$ 辺数 $E$ の有向グラフを強連結成分に分解します。

強連結成分とは、その成分内の任意の2頂点間に互いに到達可能な経路が存在する極大な部分グラフです。

Function

Constructor

StronglyConnectedComponents(Graph<WeightType> &graph)

有向グラフ $G$ を頂点数 $V$ 辺数 $E$ の graph で初期化し、強連結成分に分解します。
各成分はトポロジカル順序でソートされます。

制約

$G$ は有向グラフ

計算量

$\textrm{O}(V + E)$

Components

vector<vector<Vertex>> &Components()

強連結成分のリストを返します。
各成分は頂点のリストとして表現されます。
成分はトポロジカル順序でソートされています。

計算量

$\textrm{O}(1)$

ComponentCount

int ComponentCount() const

強連結成分の個数を返します。

計算量

$\textrm{O}(1)$

BelongComponent

int BelongComponent(const Vertex &v) const

頂点 $v$ が属する強連結成分の番号を返します。
成分番号はトポロジカル順序に対応します。

制約

$0 \le v \lt V$

計算量

$\textrm{O}(1)$

TopologicalSort

vector<Vertex> TopologicalSort() const

強連結成分のトポロジカルソート順に頂点を並べた配列を返します。
DAG（有向非巡回グラフ）においてトポロジカルソートとして使用できます。

計算量

$\textrm{O}(V)$

ContractedGraph

Graph<WeightType> ContractedGraph() const

各強連結成分を1つの頂点に縮約したグラフを返します。
縮約後のグラフは DAG（有向非巡回グラフ）になります。
同一成分内の辺は削除されます。

計算量

$\textrm{O}(V + E)$

operator[]

int operator[](const Vertex &v)
const int operator[](const Vertex &v) const

頂点 $v$ が属する強連結成分の番号を返します。
BelongComponent(v) と同等です。

制約

$0 \le v \lt V$

計算量

$\textrm{O}(1)$

Depends on

Verified with

Code

#include "Graph.hpp"
#include "GraphMisc.hpp"

template<typename WeightType>
struct StronglyConnectedComponents{
    public:
    StronglyConnectedComponents(Graph<WeightType> &graph) :
        G(graph), RG(ReverseGraph(graph)), V(G.VertexSize()), belong_(V, -1){
        vector<int> label(V, -1);
        vector<bool> state(V, false);
        int nex = 0;
        vector<Vertex> vs(V);
        iota(vs.begin(), vs.end(), 0);
        for(auto v : vs){
            if(!state[v]) dfs1(v, label, nex, state);
        }
        sort(vs.begin(), vs.end(), [&](Vertex u, Vertex v){
            return label[u] > label[v];
        });
        for(auto v : vs){
            if(state[v]){
                int c = components_.size();
                components_.push_back(vector<Vertex>{});
                dfs2(v, label, c, state);
            }
        }
    }

    inline vector<vector<Vertex>> &Components(){
        return components_;
    }

    inline int ComponentCount() const {
        return (int)components_.size();
    }

    inline int BelongComponent(const Vertex &v) const {
        return belong_[v];
    }

    vector<Vertex> TopologicalSort() const {
        vector<Vertex> ret;
        for(const auto &vs : components_){
            for(const auto &v : vs){
                ret.emplace_back(v);
            }
        }
        return ret;
    }
    
    Graph<WeightType> ContractedGraph() const {
        int nn = ComponentCount();
        Graph<WeightType> ret(nn);
        for(int u = 0; u < V; ++u){
            int nu = BelongComponent(u);
            for(const Edge<WeightType> &e : G[u]){
                int nv = BelongComponent(e.to);
                if(nu == nv) continue;
                ret.AddDirectedEdge(nu, nv, e.cost);
            }
        }
        return ret;
    }

    inline int operator[](const Vertex &v){
        return BelongComponent(v);
    }

    inline const int operator[](const Vertex &v) const {
        return BelongComponent(v);
    }

    private:
    Graph<WeightType> &G;
    Graph<WeightType> RG;
    int V;
    vector<vector<Vertex>> components_;
    vector<int> belong_;

    void dfs1(Vertex v, vector<int> &label, int &nex, vector<bool> &state){
        state[v] = true;
        for(const Edge<WeightType> &e : G[v]){
            if(state[e.to]) continue;
            dfs1(e.to, label, nex, state);
        }
        label[v] = nex++;
        return;
    }

    void dfs2(Vertex v, vector<int> &label, int component, vector<bool> &state){
        components_[component].push_back(v);
        belong_[v] = component;
        state[v] = false;
        for(const Edge<WeightType> &e : RG[v]){
            if(!state[e.to]) continue;
            dfs2(e.to, label, component, state);
        }
        return;
    }
};

#line 2 "Library/Graph/Graph.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/Graph/Graph.hpp"

using Vertex = int;

template<typename WeightType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, WeightType weight_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(weight_), idx(idx_){}
    
    bool operator<(const Edge<WeightType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    WeightType cost;
    int idx;
};

template<typename WeightType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int V) : edge_size_(0), adjacent_list_(V){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<WeightType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return adjacent_list_.size();
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<WeightType>> &operator[](const Vertex v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<WeightType>> &operator[](const Vertex v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t edge_size_;
    vector<vector<Edge<WeightType>>> adjacent_list_;
};

template<typename WeightType = int32_t>
Graph<WeightType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<WeightType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}
#line 2 "Library/Graph/GraphMisc.hpp"

#line 4 "Library/Graph/GraphMisc.hpp"

template<typename WeightType>
vector<Edge<WeightType>> ConvertEdgeSet(const Graph<WeightType> &G){
    vector<Edge<WeightType>> ret;
    vector<bool> check(G.EdgeSize(), false);
    int n = G.VertexSize();
    for(int u = 0; u < n; ++u){
        for(const Edge<WeightType> &e : G[u]){
            if(check[e.idx]) continue;
            check[e.idx] = true;
            ret.push_back(e);
        }
    }
    return ret;
}

template<typename WeightType>
vector<vector<WeightType>> ConvertDistanceMatrix(const Graph<WeightType> &G){
    int n = G.VertexSize();
    vector<vector<WeightType>> ret(n, vector<WeightType>(n, WeightType(INF)));
    for(int u = 0; u < n; ++u){
        ret[u][u] = WeightType(0);
        for(const Edge<WeightType> &e : G[u]){
            ret[u][e.to] = e.cost;
        }
    }
    return ret;
}

template<typename WeightType>
Graph<WeightType> ReverseGraph(const Graph<WeightType> &G){
    int n = G.VertexSize();
    Graph<WeightType> ret(n);
    for(int u = 0; u < n; ++u){
        for(const Edge<WeightType> &e : G[u]){
            ret.AddDirectedEdge(e.to, e.from, e.cost);
        }
    }
    return ret;
}
#line 3 "Library/Graph/StronglyConnectedComponents.hpp"

template<typename WeightType>
struct StronglyConnectedComponents{
    public:
    StronglyConnectedComponents(Graph<WeightType> &graph) :
        G(graph), RG(ReverseGraph(graph)), V(G.VertexSize()), belong_(V, -1){
        vector<int> label(V, -1);
        vector<bool> state(V, false);
        int nex = 0;
        vector<Vertex> vs(V);
        iota(vs.begin(), vs.end(), 0);
        for(auto v : vs){
            if(!state[v]) dfs1(v, label, nex, state);
        }
        sort(vs.begin(), vs.end(), [&](Vertex u, Vertex v){
            return label[u] > label[v];
        });
        for(auto v : vs){
            if(state[v]){
                int c = components_.size();
                components_.push_back(vector<Vertex>{});
                dfs2(v, label, c, state);
            }
        }
    }

    inline vector<vector<Vertex>> &Components(){
        return components_;
    }

    inline int ComponentCount() const {
        return (int)components_.size();
    }

    inline int BelongComponent(const Vertex &v) const {
        return belong_[v];
    }

    vector<Vertex> TopologicalSort() const {
        vector<Vertex> ret;
        for(const auto &vs : components_){
            for(const auto &v : vs){
                ret.emplace_back(v);
            }
        }
        return ret;
    }
    
    Graph<WeightType> ContractedGraph() const {
        int nn = ComponentCount();
        Graph<WeightType> ret(nn);
        for(int u = 0; u < V; ++u){
            int nu = BelongComponent(u);
            for(const Edge<WeightType> &e : G[u]){
                int nv = BelongComponent(e.to);
                if(nu == nv) continue;
                ret.AddDirectedEdge(nu, nv, e.cost);
            }
        }
        return ret;
    }

    inline int operator[](const Vertex &v){
        return BelongComponent(v);
    }

    inline const int operator[](const Vertex &v) const {
        return BelongComponent(v);
    }

    private:
    Graph<WeightType> &G;
    Graph<WeightType> RG;
    int V;
    vector<vector<Vertex>> components_;
    vector<int> belong_;

    void dfs1(Vertex v, vector<int> &label, int &nex, vector<bool> &state){
        state[v] = true;
        for(const Edge<WeightType> &e : G[v]){
            if(state[e.to]) continue;
            dfs1(e.to, label, nex, state);
        }
        label[v] = nex++;
        return;
    }

    void dfs2(Vertex v, vector<int> &label, int component, vector<bool> &state){
        components_[component].push_back(v);
        belong_[v] = component;
        state[v] = false;
        for(const Edge<WeightType> &e : RG[v]){
            if(!state[e.to]) continue;
            dfs2(e.to, label, component, state);
        }
        return;
    }
};

Strongly Connected Components - 強連結成分分解 (Library/Graph/StronglyConnectedComponents.hpp)

Strongly Connected Components - 強連結成分分解

Function

Constructor

Components

ComponentCount

BelongComponent

TopologicalSort

ContractedGraph

operator[]

Depends on

Verified with

Code

Strongly Connected Components - 強連結成分分解
(Library/Graph/StronglyConnectedComponents.hpp)