incremental_scc.hpp¶
离线处理按顺序加入有向边后的强连通变化；适合询问两点最早何时进入同一 SCC。
Complexity: Time: \(O(V + E \log (E + 1))\). Space: \(O(V + E)\).
AC 记录：incremental_scc。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E log(E + 1)). Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline SCC merge times for an edge insertion sequence.
/// For edge id, return the earliest prefix count t >= id+1 for which its
/// endpoints share an SCC, or m+1 if they never do. Thus self-loops and edges
/// inserted inside an existing SCC return id+1. Joining endpoints at these
/// times reconstructs the SCC partition after each insertion.
/// Vertices are in [0,n); m must be less than INT_MAX. Input is not modified.
inline std::vector<int>
incremental_scc_merge_times(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() < std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<int> mt(m, m + 1);
struct edge { int id, u, v; };
std::vector<edge> data;
data.reserve(m);
for (int id = 0; id < m; ++id) {
auto [u, v] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) mt[id] = id + 1;
else data.push_back({id, u, v});
}
if (data.empty()) return mt;
// All recursion nodes reuse these buffers; the edge ranges are disjoint.
std::vector<int> index(n, -1), touched;
std::vector<int> head, to, it, ord, low, bel, active;
auto compress = [&](int first, int last) {
touched.clear();
for (int i = first; i < last; ++i) {
for (int u : {data[i].u, data[i].v}) {
if (index[u] == -1) {
index[u] = int(touched.size());
touched.push_back(u);
}
}
}
for (int i = first; i < last; ++i) {
data[i].u = index[data[i].u];
data[i].v = index[data[i].v];
}
for (int u : touched) index[u] = -1;
return int(touched.size());
};
auto scc = [&](int first, int last, int size, int time) {
head.assign(std::size_t(size) + 1, 0);
for (int i = first; i < last; ++i)
if (data[i].id < time) ++head[data[i].u + 1];
for (int u = 0; u < size; ++u) head[u + 1] += head[u];
to.resize(head[size]);
it = head;
for (int i = first; i < last; ++i)
if (data[i].id < time) to[it[data[i].u]++] = data[i].v;
ord.assign(size, -1);
low.resize(size);
bel.resize(size);
active.clear();
int timer = 0, groups = 0;
auto dfs = [&](auto &self, int u) -> void {
ord[u] = low[u] = timer++;
active.push_back(u); // Tarjan's unfinished component vertices.
for (int i = head[u]; i < head[u + 1]; ++i) {
int v = to[i];
if (ord[v] == -1) {
self(self, v);
low[u] = std::min(low[u], low[v]);
} else low[u] = std::min(low[u], ord[v]);
}
if (low[u] == ord[u]) {
for (;;) {
int v = active.back();
active.pop_back();
ord[v] = size; // Completed components cannot lower low[].
bel[v] = groups;
if (v == u) break;
}
++groups;
}
};
for (int u = 0; u < size; ++u) if (ord[u] == -1) dfs(dfs, u);
};
// Edges crossing final SCCs never get a finite merge time.
int size = compress(0, int(data.size()));
scc(0, int(data.size()), size, m);
int keep = 0;
for (auto e : data) if (bel[e.u] == bel[e.v]) data[keep++] = e;
data.resize(keep);
auto dfs = [&](auto &self, int first, int last, int lo, int hi) -> void {
for (int i = first; i < last;) {
auto e = data[i];
if (e.u == e.v) {
// A right-half contraction merged these endpoints before insertion.
mt[e.id] = e.id + 1;
std::swap(data[i], data[--last]);
} else ++i;
}
if (first == last) return;
if (hi - lo == 1) {
for (int i = first; i < last; ++i) mt[data[i].id] = hi;
return;
}
int mid = lo + (hi - lo) / 2;
int size = compress(first, last);
scc(first, last, size, mid);
int split = first;
for (int i = first; i < last; ++i) {
auto &e = data[i];
if (e.id < mid && bel[e.u] == bel[e.v]) {
std::swap(data[split++], e);
} else {
e.u = bel[e.u];
e.v = bel[e.v];
}
}
self(self, first, split, lo, mid);
self(self, split, last, mid, hi);
};
dfs(dfs, 0, int(data.size()), 0, m);
return mt;
}
/// @brief After each insertion, sum wt[u]*wt[v] over unordered distinct
/// vertex pairs in the same SCC. T supports zero, += and multiplication;
/// all intermediate values must be representable. Input is not modified.
template <class T>
std::vector<T>
incremental_scc_pair_product_sums(const std::vector<T> &wt,
const std::vector<std::pair<int, int>> &es) {
if (es.empty()) return {};
int n = int(wt.size());
auto mt = incremental_scc_merge_times(n, es);
int m = int(es.size());
std::vector<int> head(m + 1, -1), next(m);
// Prepend in descending order to preserve ascending IDs at each time.
for (int id = m; id-- > 0;) if (mt[id] <= m) {
next[id] = head[mt[id]];
head[mt[id]] = id;
}
std::vector<int> fa(n, -1);
std::vector<T> sum = wt;
auto rt = [&](int u) {
int root = u;
while (fa[root] >= 0) root = fa[root];
while (u != root) {
int p = fa[u];
fa[u] = root;
u = p;
}
return root;
};
T tot{};
std::vector<T> res(m);
for (int time = 1; time <= m; ++time) {
for (int id = head[time]; id != -1; id = next[id]) {
int a = rt(es[id].first), b = rt(es[id].second);
if (a == b) continue;
tot += sum[a] * sum[b];
if (fa[a] > fa[b]) std::swap(a, b);
fa[a] += fa[b];
fa[b] = a;
sum[a] += sum[b];
}
res[time - 1] = tot;
}
return res;
}
} // namespace noya
// NOYA_INCREMENTAL_SCC_HPP
#ifndef NOYA_INCREMENTAL_SCC_HPP
#define NOYA_INCREMENTAL_SCC_HPP 1
/// @complexity Time: O(V + E log(E + 1)). Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline SCC merge times for an edge insertion sequence.
/// For edge id, return the earliest prefix count t >= id+1 for which its
/// endpoints share an SCC, or m+1 if they never do. Thus self-loops and edges
/// inserted inside an existing SCC return id+1. Joining endpoints at these
/// times reconstructs the SCC partition after each insertion.
/// Vertices are in [0,n); m must be less than INT_MAX. Input is not modified.
inline std::vector<int>
incremental_scc_merge_times(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() < std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<int> mt(m, m + 1);
struct edge { int id, u, v; };
std::vector<edge> data;
data.reserve(m);
for (int id = 0; id < m; ++id) {
auto [u, v] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) mt[id] = id + 1;
else data.push_back({id, u, v});
}
if (data.empty()) return mt;
// All recursion nodes reuse these buffers; the edge ranges are disjoint.
std::vector<int> index(n, -1), touched;
std::vector<int> head, to, it, ord, low, bel, active;
auto compress = [&](int first, int last) {
touched.clear();
for (int i = first; i < last; ++i) {
for (int u : {data[i].u, data[i].v}) {
if (index[u] == -1) {
index[u] = int(touched.size());
touched.push_back(u);
}
}
}
for (int i = first; i < last; ++i) {
data[i].u = index[data[i].u];
data[i].v = index[data[i].v];
}
for (int u : touched) index[u] = -1;
return int(touched.size());
};
auto scc = [&](int first, int last, int size, int time) {
head.assign(std::size_t(size) + 1, 0);
for (int i = first; i < last; ++i)
if (data[i].id < time) ++head[data[i].u + 1];
for (int u = 0; u < size; ++u) head[u + 1] += head[u];
to.resize(head[size]);
it = head;
for (int i = first; i < last; ++i)
if (data[i].id < time) to[it[data[i].u]++] = data[i].v;
ord.assign(size, -1);
low.resize(size);
bel.resize(size);
active.clear();
int timer = 0, groups = 0;
auto dfs = [&](auto &self, int u) -> void {
ord[u] = low[u] = timer++;
active.push_back(u); // Tarjan's unfinished component vertices.
for (int i = head[u]; i < head[u + 1]; ++i) {
int v = to[i];
if (ord[v] == -1) {
self(self, v);
low[u] = std::min(low[u], low[v]);
} else low[u] = std::min(low[u], ord[v]);
}
if (low[u] == ord[u]) {
for (;;) {
int v = active.back();
active.pop_back();
ord[v] = size; // Completed components cannot lower low[].
bel[v] = groups;
if (v == u) break;
}
++groups;
}
};
for (int u = 0; u < size; ++u) if (ord[u] == -1) dfs(dfs, u);
};
// Edges crossing final SCCs never get a finite merge time.
int size = compress(0, int(data.size()));
scc(0, int(data.size()), size, m);
int keep = 0;
for (auto e : data) if (bel[e.u] == bel[e.v]) data[keep++] = e;
data.resize(keep);
auto dfs = [&](auto &self, int first, int last, int lo, int hi) -> void {
for (int i = first; i < last;) {
auto e = data[i];
if (e.u == e.v) {
// A right-half contraction merged these endpoints before insertion.
mt[e.id] = e.id + 1;
std::swap(data[i], data[--last]);
} else ++i;
}
if (first == last) return;
if (hi - lo == 1) {
for (int i = first; i < last; ++i) mt[data[i].id] = hi;
return;
}
int mid = lo + (hi - lo) / 2;
int size = compress(first, last);
scc(first, last, size, mid);
int split = first;
for (int i = first; i < last; ++i) {
auto &e = data[i];
if (e.id < mid && bel[e.u] == bel[e.v]) {
std::swap(data[split++], e);
} else {
e.u = bel[e.u];
e.v = bel[e.v];
}
}
self(self, first, split, lo, mid);
self(self, split, last, mid, hi);
};
dfs(dfs, 0, int(data.size()), 0, m);
return mt;
}
/// @brief After each insertion, sum wt[u]*wt[v] over unordered distinct
/// vertex pairs in the same SCC. T supports zero, += and multiplication;
/// all intermediate values must be representable. Input is not modified.
template <class T>
std::vector<T>
incremental_scc_pair_product_sums(const std::vector<T> &wt,
const std::vector<std::pair<int, int>> &es) {
if (es.empty()) return {};
int n = int(wt.size());
auto mt = incremental_scc_merge_times(n, es);
int m = int(es.size());
std::vector<int> head(m + 1, -1), next(m);
// Prepend in descending order to preserve ascending IDs at each time.
for (int id = m; id-- > 0;) if (mt[id] <= m) {
next[id] = head[mt[id]];
head[mt[id]] = id;
}
std::vector<int> fa(n, -1);
std::vector<T> sum = wt;
auto rt = [&](int u) {
int root = u;
while (fa[root] >= 0) root = fa[root];
while (u != root) {
int p = fa[u];
fa[u] = root;
u = p;
}
return root;
};
T tot{};
std::vector<T> res(m);
for (int time = 1; time <= m; ++time) {
for (int id = head[time]; id != -1; id = next[id]) {
int a = rt(es[id].first), b = rt(es[id].second);
if (a == b) continue;
tot += sum[a] * sum[b];
if (fa[a] > fa[b]) std::swap(a, b);
fa[a] += fa[b];
fa[b] = a;
sum[a] += sum[b];
}
res[time - 1] = tot;
}
return res;
}
} // namespace noya
#endif // NOYA_INCREMENTAL_SCC_HPP
/// @complexity Time: O(V + E log(E + 1)). Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline SCC merge times for an edge insertion sequence.
/// For edge id, return the earliest prefix count t >= id+1 for which its
/// endpoints share an SCC, or m+1 if they never do. Thus self-loops and edges
/// inserted inside an existing SCC return id+1. Joining endpoints at these
/// times reconstructs the SCC partition after each insertion.
/// Vertices are in [0,n); m must be less than INT_MAX. Input is not modified.
inline std::vector<int>
incremental_scc_merge_times(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() < std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<int> mt(m, m + 1);
struct edge { int id, u, v; };
std::vector<edge> data;
data.reserve(m);
for (int id = 0; id < m; ++id) {
auto [u, v] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) mt[id] = id + 1;
else data.push_back({id, u, v});
}
if (data.empty()) return mt;
// All recursion nodes reuse these buffers; the edge ranges are disjoint.
std::vector<int> index(n, -1), touched;
std::vector<int> head, to, it, ord, low, bel, active;
auto compress = [&](int first, int last) {
touched.clear();
for (int i = first; i < last; ++i) {
for (int u : {data[i].u, data[i].v}) {
if (index[u] == -1) {
index[u] = int(touched.size());
touched.push_back(u);
}
}
}
for (int i = first; i < last; ++i) {
data[i].u = index[data[i].u];
data[i].v = index[data[i].v];
}
for (int u : touched) index[u] = -1;
return int(touched.size());
};
auto scc = [&](int first, int last, int size, int time) {
head.assign(std::size_t(size) + 1, 0);
for (int i = first; i < last; ++i)
if (data[i].id < time) ++head[data[i].u + 1];
for (int u = 0; u < size; ++u) head[u + 1] += head[u];
to.resize(head[size]);
it = head;
for (int i = first; i < last; ++i)
if (data[i].id < time) to[it[data[i].u]++] = data[i].v;
ord.assign(size, -1);
low.resize(size);
bel.resize(size);
active.clear();
int timer = 0, groups = 0;
auto dfs = [&](auto &self, int u) -> void {
ord[u] = low[u] = timer++;
active.push_back(u); // Tarjan's unfinished component vertices.
for (int i = head[u]; i < head[u + 1]; ++i) {
int v = to[i];
if (ord[v] == -1) {
self(self, v);
low[u] = std::min(low[u], low[v]);
} else low[u] = std::min(low[u], ord[v]);
}
if (low[u] == ord[u]) {
for (;;) {
int v = active.back();
active.pop_back();
ord[v] = size; // Completed components cannot lower low[].
bel[v] = groups;
if (v == u) break;
}
++groups;
}
};
for (int u = 0; u < size; ++u) if (ord[u] == -1) dfs(dfs, u);
};
// Edges crossing final SCCs never get a finite merge time.
int size = compress(0, int(data.size()));
scc(0, int(data.size()), size, m);
int keep = 0;
for (auto e : data) if (bel[e.u] == bel[e.v]) data[keep++] = e;
data.resize(keep);
auto dfs = [&](auto &self, int first, int last, int lo, int hi) -> void {
for (int i = first; i < last;) {
auto e = data[i];
if (e.u == e.v) {
// A right-half contraction merged these endpoints before insertion.
mt[e.id] = e.id + 1;
std::swap(data[i], data[--last]);
} else ++i;
}
if (first == last) return;
if (hi - lo == 1) {
for (int i = first; i < last; ++i) mt[data[i].id] = hi;
return;
}
int mid = lo + (hi - lo) / 2;
int size = compress(first, last);
scc(first, last, size, mid);
int split = first;
for (int i = first; i < last; ++i) {
auto &e = data[i];
if (e.id < mid && bel[e.u] == bel[e.v]) {
std::swap(data[split++], e);
} else {
e.u = bel[e.u];
e.v = bel[e.v];
}
}
self(self, first, split, lo, mid);
self(self, split, last, mid, hi);
};
dfs(dfs, 0, int(data.size()), 0, m);
return mt;
}
/// @brief After each insertion, sum wt[u]*wt[v] over unordered distinct
/// vertex pairs in the same SCC. T supports zero, += and multiplication;
/// all intermediate values must be representable. Input is not modified.
template <class T>
std::vector<T>
incremental_scc_pair_product_sums(const std::vector<T> &wt,
const std::vector<std::pair<int, int>> &es) {
if (es.empty()) return {};
int n = int(wt.size());
auto mt = incremental_scc_merge_times(n, es);
int m = int(es.size());
std::vector<int> head(m + 1, -1), next(m);
// Prepend in descending order to preserve ascending IDs at each time.
for (int id = m; id-- > 0;) if (mt[id] <= m) {
next[id] = head[mt[id]];
head[mt[id]] = id;
}
std::vector<int> fa(n, -1);
std::vector<T> sum = wt;
auto rt = [&](int u) {
int root = u;
while (fa[root] >= 0) root = fa[root];
while (u != root) {
int p = fa[u];
fa[u] = root;
u = p;
}
return root;
};
T tot{};
std::vector<T> res(m);
for (int time = 1; time <= m; ++time) {
for (int id = head[time]; id != -1; id = next[id]) {
int a = rt(es[id].first), b = rt(es[id].second);
if (a == b) continue;
tot += sum[a] * sum[b];
if (fa[a] > fa[b]) std::swap(a, b);
fa[a] += fa[b];
fa[b] = a;
sum[a] += sum[b];
}
res[time - 1] = tot;
}
return res;
}
} // namespace noya
// NOYA_INCREMENTAL_SCC_HPP