SCC Graph
(graph/scc_graph.hpp)

• View this file on GitHub
• Last update: 2023-05-26 21:39:22+09:00
• Include: #include "graph/scc_graph.hpp"

説明

強連結成分分解をする。 $O(N + M)$

コンストラクタ

scc_graph(int n) $n$ 頂点のグラフを定義

add_edge(int from, int to)

from から to に辺を貼る

scc()

強連結成分分解をする。 $1$ 回しか読んだらダメ

same(int u, int v)

u と v が強連結成分分解後に同一の成分にあるか判定。

scc_id()

各頂点の強連結成分分解後の属する頂点番号の配列を返す。

create_graph()

強連結成分分解後のグラフを陽に構築

Depends on

• テンプレート (template/template.hpp)

Required by

• Two SAT (math/two_sat.hpp)

Verified with

• test/math/aoj_3205.test.cpp
• test/math/two_sat.test.cpp

Code

#pragma once

#include "../template/template.hpp"

namespace lib {

struct scc_graph {
    vector<vector<int>> g, rg;
    int n, k;

    vector<int> vs, cmp;
    vector<int> seen;

    void dfs(int v) {
        seen[v] = 1;
        for (auto &nv : g[v]) {
            if (seen[nv] < 0) dfs(nv);
        }
        vs.emplace_back(v);
    }

    void rdfs(int v) {
        cmp[v] = k;
        for (auto nv : rg[v]) {
            if (cmp[nv] < 0) rdfs(nv);
        }
    }

    scc_graph(int n) : n(n) {
        g.resize(n);
        rg.resize(n);
    }

    void add_edge(int from, int to) {
        g[from].emplace_back(to);
        rg[to].emplace_back(from);
    }

    void scc() {
        seen.assign(n, -1);
        rep(i, 0, n) {
            if (seen[i] < 0) dfs(i);
        }
        reverse(all(vs));
        cmp.assign(n, -1);
        k = 0;
        for (auto &v : vs) {
            if (cmp[v] < 0) {
                rdfs(v);
                k++;
            }
        }
    }

    bool same(int u, int v) {
        return cmp[u] == cmp[v];
    }

    vector<int> scc_id() {
        return cmp;
    }

    vector<vector<int>> create_graph() {
        vector<vector<int>> t(k);
        rep(i, 0, n) {
            int v = cmp[i];
            for (auto to : g[i]) {
                int nv = cmp[to];
                if (v == nv) continue;
                t[v].emplace_back(nv);
            }
        }
        rep(i, 0, k) {
            sort(all(t[i]));
            t[i].erase(unique(all(t[i])), t[i].end());
        }
        return t;
    }
};

}

#line 2 "graph/scc_graph.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "graph/scc_graph.hpp"

namespace lib {

struct scc_graph {
    vector<vector<int>> g, rg;
    int n, k;

    vector<int> vs, cmp;
    vector<int> seen;

    void dfs(int v) {
        seen[v] = 1;
        for (auto &nv : g[v]) {
            if (seen[nv] < 0) dfs(nv);
        }
        vs.emplace_back(v);
    }

    void rdfs(int v) {
        cmp[v] = k;
        for (auto nv : rg[v]) {
            if (cmp[nv] < 0) rdfs(nv);
        }
    }

    scc_graph(int n) : n(n) {
        g.resize(n);
        rg.resize(n);
    }

    void add_edge(int from, int to) {
        g[from].emplace_back(to);
        rg[to].emplace_back(from);
    }

    void scc() {
        seen.assign(n, -1);
        rep(i, 0, n) {
            if (seen[i] < 0) dfs(i);
        }
        reverse(all(vs));
        cmp.assign(n, -1);
        k = 0;
        for (auto &v : vs) {
            if (cmp[v] < 0) {
                rdfs(v);
                k++;
            }
        }
    }

    bool same(int u, int v) {
        return cmp[u] == cmp[v];
    }

    vector<int> scc_id() {
        return cmp;
    }

    vector<vector<int>> create_graph() {
        vector<vector<int>> t(k);
        rep(i, 0, n) {
            int v = cmp[i];
            for (auto to : g[i]) {
                int nv = cmp[to];
                if (v == nv) continue;
                t[v].emplace_back(nv);
            }
        }
        rep(i, 0, k) {
            sort(all(t[i]));
            t[i].erase(unique(all(t[i])), t[i].end());
        }
        return t;
    }
};

}

Back to top page