offline incremental SCC
(Src/Graph/Components/IncrementalSCC.hpp)

View this file on GitHub
Last update: 2024-06-28 18:38:15+09:00
Include: #include "Src/Graph/Components/IncrementalSCC.hpp"

概要

$M$ 要素からなる有向辺の列 $E = ((u_{1}, v_{1}), (u_{2}, v_{2}), \dots, (u_{M}, v_{M}))$ が与えられる。

$N$ 頂点 $0$ 辺のグラフ $G$ に対して $E$ の辺をこの順に追加していく。

$E$ の各辺 $(u_{i}, v_{i})$ についてその辺の両端点が強連結になる時間を計算する。

使い方

コンストラクタ

(1) IncrementalSCC() = default;
(2) IncrementalSCC(usize n)

(2) $n$ 頂点 $0$ 辺のグラフを用意する。 $E = ()$ とする。

size

inline u32 size() const noexcept

グラフの頂点数を返す。

addEdge

u32 addEdge(VType u, VType v)

VType = u32

$E$ の末尾に $u$ から $v$ へ伸びる辺を追加する。この辺が何番目に追加された辺かを0-indexedで返す。

getEdge

std::pair<VType, VType> getEdge(TimeType t) const

0-indexedで $t$ 番目に追加された辺を返す。firstからsecondへ向けて張られた辺である。

build

IncrementalSCCResponse build() const

$E$ の各辺 $(u_{i}, v_{i})$ について、頂点 $u_{i}, v_{i}$ が強連結になる時間を計算する。

計算量: $O(

\log

IncrementalSCCResponse

invalid

static constexpr TimeType invalid() noexcept

最後まで強連結にならないことを示す特別な値を返す。

operator[]

TimeType operator[](u32 i) const noexcept

$(u_{i}, v_{i})$ について頂点 $u_{i}, v_{i}$ が強連結になる時間を返す。

厳密には、 $E$ の $0$ 番目から $t$ 番目までの辺を追加すると $u_{i}, v_{i}$ が強連結になるような最小の $t$ を返す。

そのような $t$ が存在しなければinvalid()を返す。

計算量: $O(1)$

same

bool same(u32 i) const noexcept

$(u_{i}, v_{i})$ が最終的に強連結になるかを返す。

メモ

$(u_{i}, v_{i})$ が強連結になる時間を $T_{i}$ とする。

頂点 $u_{i}, v_{i}$ にコスト $T_{i}$ の無向辺を張ったグラフを考える。

このグラフ上で最小全域木を張る。木上の $u-v$ パスに含まれるコスト最大の辺のコスト $T$ が頂点 $u, v$ が強連結になる時間と一致する。

参考

My own algorithm – offline incremental strongly connected components in O(mlog(m))

Depends on

標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "atcoder/scc.hpp"

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class IncrementalSCCResponse {
public:
    using TimeType = u32;
    static constexpr TimeType invalid() noexcept {
        return INVALID;
    }
    IncrementalSCCResponse() = default;
    IncrementalSCCResponse(const std::vector<TimeType>& T) : time_{T} {
        time_.shrink_to_fit();
    }
    TimeType operator[](u32 i) const noexcept {
        assert(i < time_.size());
        return time_[i];
    }
    bool same(u32 i) const noexcept {
        return time_[i] != INVALID;
    }
private:
    static constexpr TimeType INVALID{static_cast<TimeType>(-1)};
    std::vector<TimeType> time_;
};

class IncrementalSCC {
private:
    using TimeType = IncrementalSCCResponse::TimeType;
    using VType = u32;
    using Edge = std::tuple<TimeType, VType, VType>;
    static constexpr u32 INVALID{IncrementalSCCResponse::invalid()};

    usize n_;
    std::vector<Edge> edges_;
public:
    IncrementalSCC() = default;
    IncrementalSCC(usize n) : n_{n}, edges_{} {}

    inline u32 size() const noexcept {
        return n_;
    }

    constexpr u32 invalid() const noexcept {
        return INVALID;
    }

    u32 addEdge(VType u, VType v) {
        assert(u < n_);
        assert(v < n_);
        TimeType t{static_cast<TimeType>(edges_.size())};
        edges_.emplace_back(t, u, v);
        return t;
    }

    std::pair<VType, VType> getEdge(TimeType t) const {
        assert(t < edges_.size());
        auto [_, u, v]{edges_[t]};
        return std::pair<VType, VType>{ u, v };
    }

    IncrementalSCCResponse build() const {
        std::vector<VType> id(size(), INVALID);
        std::vector<TimeType> res(edges_.size(), INVALID);
        auto rec{[&](auto rec, u32 L, u32 R, const std::vector<Edge>& E) -> void {
            if (E.empty() or L + 1 >= R) {
                return;
            }
            u32 n{};
            for (auto [t, u, v] : E) {
                if (id[u] == INVALID) {
                    id[u] = n++;
                }
                if (id[v] == INVALID) {
                    id[v] = n++;
                }
            }
            u32 mid{(L + R) >> 1};
            atcoder::scc_graph g(n);
            for (auto [t, u, v] : E) {
                if (t < mid) {
                    g.add_edge(id[u], id[v]);
                }
            }
            auto scc{g.scc()};
            std::vector<u32> comp(n);
            for (u32 i{} ; i < scc.size() ; i++) {
                for (auto v : scc[i]) {
                    comp[v] = i;
                }
            }
            std::vector<Edge> EL, ER;
            for (auto [t, u, v] : E) {
                u = id[u];
                v = id[v];
                if (t < mid and comp[u] == comp[v]) {
                    res[t] = std::min(res[t], mid - 1);
                    EL.emplace_back(t, u, v);
                }
                else {
                    ER.emplace_back(t, comp[u], comp[v]);
                }
            }
            for (auto [_, u, v] : E) {
                id[u] = id[v] = INVALID;
            }
            rec(rec, L, mid, EL);
            rec(rec, mid, R, ER);
        }};
        rec(rec, u32{}, edges_.size() + 1, edges_);
        return IncrementalSCCResponse{res};
    }
};

} // namespace zawa

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/scc.hpp: line -1: no such header

offline incremental SCC (Src/Graph/Components/IncrementalSCC.hpp)

概要

使い方