Incremental SCC （強連結成分）
(graph/incremental_scc.hpp)

View this file on GitHub
Last update: 2024-07-06 10:40:57+09:00
Include: #include "graph/incremental_scc.hpp"
Link: https://codeforces.com/contest/1989/submission/268026664

$m$ 個の有向辺からなる列が与えられ，先頭の要素から順にグラフに追加していく．各有向辺について，グラフに何番目の辺まで追加したときに初めてその辺を含む閉路ができるかを $O(m \log m)$ で計算する．

この処理は以下のような用途に使える．

UnionFind などのデータ構造を併用することで，各時点での強連結成分を管理できる．
各辺を含む閉路ができる時刻を重みとして最小全域木を求め，更に heavy-light decomposition やセグメント木と併用することで， 2 頂点が同一の強連結成分に初めて属する時刻をクエリ $O(n \log n)$ 等で計算できる．

使用方法

vector<pair<int, int>> edges;  // 有向辺の列． edges[i] は時刻 i に追加される

auto ticks = incremental_scc(edges);

assert(ticks.size() == edges.size());
// ticks[i] = (edges[i] を含む閉路ができる時刻 (0 <= ticks[i] < m)) または m （閉路ができない場合・自己ループの場合）

問題例

Educational Codeforces Round 167 (Rated for Div. 2) F. Simultaneous Coloring

リンク

My own algorithm — offline incremental strongly connected components in O(m*log(m)) - Codeforces

Code

#pragma once

#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>

#include "graph/strongly_connected_components.hpp"

// edges[i] = (s, t) means that the edge (s, t) is added at i-th tick.
// Return the earliest tick when the edge (s, t) is included in a cycle.
// If the edge (s, t) is never included in a cycle or s == t, return M.
// Complexity: O(M log M), where M = edges.size()
// Verified: https://codeforces.com/contest/1989/submission/268026664
std::vector<int> incremental_scc(const std::vector<std::pair<int, int>> &edges) {
    int N = 1;
    for (auto [s, t] : edges) N = std::max({N, s + 1, t + 1});

    const int M = edges.size();

    std::vector<int> ret(M, M);

    std::vector<int> compressed_idx(N, -1);

    using Edges = std::vector<std::tuple<int, int, int>>;

    auto rec = [&](auto &&self, const Edges &e, int tl, int tr) -> void {
        if (e.empty() or tl + 1 == tr) return;

        int n = 0;
        for (const auto &[tick, s, t] : e) {
            if (compressed_idx.at(s) == -1) compressed_idx.at(s) = n++;
            if (compressed_idx.at(t) == -1) compressed_idx.at(t) = n++;
        }

        const int tmid = (tl + tr) / 2;

        DirectedGraphSCC scc(n);
        for (const auto &[tick, s, t] : e) {
            if (tick < tmid) scc.add_edge(compressed_idx.at(s), compressed_idx.at(t));
        }
        scc.FindStronglyConnectedComponents();

        Edges left, right;

        for (const auto &[tick, s, t] : e) {
            const int sc = compressed_idx.at(s), tc = compressed_idx.at(t);
            if (tick < tmid and scc.cmp.at(sc) == scc.cmp.at(tc)) {
                ret.at(tick) = tmid - 1;
                left.emplace_back(tick, sc, tc);
            } else {
                right.emplace_back(tick, scc.cmp.at(sc), scc.cmp.at(tc));
            }
        }

        for (auto [_, s, t] : e) compressed_idx.at(s) = compressed_idx.at(t) = -1;

        self(self, left, tl, tmid);
        self(self, right, tmid, tr);
    };

    Edges init;
    init.reserve(M);
    for (int tick = 0; tick < M; ++tick) {
        if (auto [s, t] = edges.at(tick); s != t) init.emplace_back(tick, s, t);
    }

    rec(rec, init, 0, M + 1);

    return ret;
}

#line 2 "graph/incremental_scc.hpp"

#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>

#line 3 "graph/strongly_connected_components.hpp"
#include <cassert>
#line 5 "graph/strongly_connected_components.hpp"

// CUT begin
// Directed graph library to find strongly connected components （強連結成分分解）
// 0-indexed directed graph
// Complexity: O(V + E)
struct DirectedGraphSCC {
    int V; // # of Vertices
    std::vector<std::vector<int>> to, from;
    std::vector<int> used; // Only true/false
    std::vector<int> vs;
    std::vector<int> cmp;
    int scc_num = -1;

    DirectedGraphSCC(int V = 0) : V(V), to(V), from(V), cmp(V) {}

    void _dfs(int v) {
        used[v] = true;
        for (auto t : to[v])
            if (!used[t]) _dfs(t);
        vs.push_back(v);
    }
    void _rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (auto t : from[v])
            if (!used[t]) _rdfs(t, k);
    }

    void add_edge(int from_, int to_) {
        assert(from_ >= 0 and from_ < V and to_ >= 0 and to_ < V);
        to[from_].push_back(to_);
        from[to_].push_back(from_);
    }

    // Detect strongly connected components and return # of them.
    // Also, assign each vertex `v` the scc id `cmp[v]` (0-indexed)
    int FindStronglyConnectedComponents() {
        used.assign(V, false);
        vs.clear();
        for (int v = 0; v < V; v++)
            if (!used[v]) _dfs(v);
        used.assign(V, false);
        scc_num = 0;
        for (int i = (int)vs.size() - 1; i >= 0; i--)
            if (!used[vs[i]]) _rdfs(vs[i], scc_num++);
        return scc_num;
    }

    // Find and output the vertices that form a closed cycle.
    // output: {v_1, ..., v_C}, where C is the length of cycle,
    //         {} if there's NO cycle (graph is DAG)
    int _c, _init;
    std::vector<int> _ret_cycle;
    bool _dfs_detectcycle(int now, bool b0) {
        if (now == _init and b0) return true;
        for (auto nxt : to[now])
            if (cmp[nxt] == _c and !used[nxt]) {
                _ret_cycle.emplace_back(nxt), used[nxt] = 1;
                if (_dfs_detectcycle(nxt, true)) return true;
                _ret_cycle.pop_back();
            }
        return false;
    }
    std::vector<int> DetectCycle() {
        int ns = FindStronglyConnectedComponents();
        if (ns == V) return {};
        std::vector<int> cnt(ns);
        for (auto x : cmp) cnt[x]++;
        _c = std::find_if(cnt.begin(), cnt.end(), [](int x) { return x > 1; }) - cnt.begin();
        _init = std::find(cmp.begin(), cmp.end(), _c) - cmp.begin();
        used.assign(V, false);
        _ret_cycle.clear();
        _dfs_detectcycle(_init, false);
        return _ret_cycle;
    }

    // After calling `FindStronglyConnectedComponents()`, generate a new graph by uniting all
    // vertices belonging to the same component(The resultant graph is DAG).
    DirectedGraphSCC GenerateTopologicalGraph() {
        DirectedGraphSCC newgraph(scc_num);
        for (int s = 0; s < V; s++)
            for (auto t : to[s]) {
                if (cmp[s] != cmp[t]) newgraph.add_edge(cmp[s], cmp[t]);
            }
        return newgraph;
    }
};

// 2-SAT solver: Find a solution for  `(Ai v Aj) ^ (Ak v Al) ^ ... = true`
// - `nb_sat_vars`: Number of variables
// - Considering a graph with `2 * nb_sat_vars` vertices
// - Vertices [0, nb_sat_vars) means `Ai`
// - vertices [nb_sat_vars, 2 * nb_sat_vars) means `not Ai`
struct SATSolver : DirectedGraphSCC {
    int nb_sat_vars;
    std::vector<int> solution;
    SATSolver(int nb_variables = 0)
        : DirectedGraphSCC(nb_variables * 2), nb_sat_vars(nb_variables), solution(nb_sat_vars) {}
    void add_x_or_y_constraint(bool is_x_true, int x, bool is_y_true, int y) {
        assert(x >= 0 and x < nb_sat_vars);
        assert(y >= 0 and y < nb_sat_vars);
        if (!is_x_true) x += nb_sat_vars;
        if (!is_y_true) y += nb_sat_vars;
        add_edge((x + nb_sat_vars) % (nb_sat_vars * 2), y);
        add_edge((y + nb_sat_vars) % (nb_sat_vars * 2), x);
    }
    // Solve the 2-SAT problem. If no solution exists, return `false`.
    // Otherwise, dump one solution to `solution` and return `true`.
    bool run() {
        FindStronglyConnectedComponents();
        for (int i = 0; i < nb_sat_vars; i++) {
            if (cmp[i] == cmp[i + nb_sat_vars]) return false;
            solution[i] = cmp[i] > cmp[i + nb_sat_vars];
        }
        return true;
    }
};
#line 9 "graph/incremental_scc.hpp"

// edges[i] = (s, t) means that the edge (s, t) is added at i-th tick.
// Return the earliest tick when the edge (s, t) is included in a cycle.
// If the edge (s, t) is never included in a cycle or s == t, return M.
// Complexity: O(M log M), where M = edges.size()
// Verified: https://codeforces.com/contest/1989/submission/268026664
std::vector<int> incremental_scc(const std::vector<std::pair<int, int>> &edges) {
    int N = 1;
    for (auto [s, t] : edges) N = std::max({N, s + 1, t + 1});

    const int M = edges.size();

    std::vector<int> ret(M, M);

    std::vector<int> compressed_idx(N, -1);

    using Edges = std::vector<std::tuple<int, int, int>>;

    auto rec = [&](auto &&self, const Edges &e, int tl, int tr) -> void {
        if (e.empty() or tl + 1 == tr) return;

        int n = 0;
        for (const auto &[tick, s, t] : e) {
            if (compressed_idx.at(s) == -1) compressed_idx.at(s) = n++;
            if (compressed_idx.at(t) == -1) compressed_idx.at(t) = n++;
        }

        const int tmid = (tl + tr) / 2;

        DirectedGraphSCC scc(n);
        for (const auto &[tick, s, t] : e) {
            if (tick < tmid) scc.add_edge(compressed_idx.at(s), compressed_idx.at(t));
        }
        scc.FindStronglyConnectedComponents();

        Edges left, right;

        for (const auto &[tick, s, t] : e) {
            const int sc = compressed_idx.at(s), tc = compressed_idx.at(t);
            if (tick < tmid and scc.cmp.at(sc) == scc.cmp.at(tc)) {
                ret.at(tick) = tmid - 1;
                left.emplace_back(tick, sc, tc);
            } else {
                right.emplace_back(tick, scc.cmp.at(sc), scc.cmp.at(tc));
            }
        }

        for (auto [_, s, t] : e) compressed_idx.at(s) = compressed_idx.at(t) = -1;

        self(self, left, tl, tmid);
        self(self, right, tmid, tr);
    };

    Edges init;
    init.reserve(M);
    for (int tick = 0; tick < M; ++tick) {
        if (auto [s, t] = edges.at(tick); s != t) init.emplace_back(tick, s, t);
    }

    rec(rec, init, 0, M + 1);

    return ret;
}

Incremental SCC （強連結成分） (graph/incremental_scc.hpp)

使用方法

問題例

リンク

Code

Incremental SCC （強連結成分）
(graph/incremental_scc.hpp)