dominator_tree.hpp¶
找从起点到某点的所有路径都必须经过的点，并组织成支配树；返回最近的严格必经点，根返回自身，不可达点返回 -1。
Complexity: Time: \(O(V + E \log (V + 1))\) with simple link-eval. Space: \(O(V + E)\).
AC 记录：dominatortree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E log(V + 1)) with simple link-eval.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Immediate dominators in a directed graph using Lengauer-Tarjan.
/// The root dominates itself; unreachable vertices have parent -1.
/// Loops and parallel edges are allowed; g is unchanged.
/// Requires a valid root, valid endpoints and an int-representable vertex count.
inline std::vector<int> dominator_tree(const std::vector<std::vector<int>> &g,
int rt) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
const int n = int(g.size());
assert(0 <= rt && rt < n);
for (const auto &row : g) {
for (int to : row) {
assert(0 <= to && to < n);
}
}
std::vector<int> ord(n, -1), vs, parent;
auto dfs = [&](auto &self, int u, int p) -> void {
ord[u] = int(vs.size());
vs.push_back(u);
parent.push_back(p);
for (int v : g[u]) if (ord[v] == -1) self(self, v, u);
};
dfs(dfs, rt, -1);
const int reached = int(vs.size());
std::vector<int> id(n, -1);
id[rt] = rt;
if (reached == 1) {
return id;
}
// Only reachable predecessors matter. Loops and edges into rt cannot
// change any immediate dominator, so omit them from the reverse CSR.
std::vector<std::size_t> start(std::size_t(n) + 1);
for (int u : vs) {
for (int v : g[u]) {
if (v != u && v != rt) {
++start[v];
}
}
}
for (int u = 0; u < n; ++u) {
start[u + 1] += start[u];
}
std::vector<int> pred(start.back());
for (int u : vs) {
for (int v : g[u]) {
if (v != u && v != rt) {
pred[--start[v]] = u;
}
}
}
// Semidominators use DFS numbers; all other labels use original vertices.
std::vector<int> semi = std::move(ord);
std::vector<int> lab(n), anc(n, -1), can(n, -1);
std::iota(lab.begin(), lab.end(), 0);
// Each vertex enters one bucket once, so one next pointer is sufficient.
std::vector<int> head(n, -1), next(n);
auto ev = [&](auto &self, int u) -> int {
if (anc[u] == -1) return lab[u];
int p = anc[u], best = self(self, p);
if (semi[best] < semi[lab[u]]) lab[u] = best;
if (anc[p] != -1) anc[u] = anc[p];
return lab[u];
};
for (int i = reached - 1; i >= 1; i--) {
int u = vs[i];
for (auto j = start[u]; j < start[u + 1]; ++j) {
semi[u] = std::min(semi[u], semi[ev(ev, pred[j])]);
}
int s = vs[semi[u]], p = parent[i];
next[u] = head[s];
head[s] = u;
for (int buf = head[p]; buf != -1; buf = next[buf]) {
can[buf] = ev(ev, buf);
}
head[p] = -1;
// Evaluate the parent's bucket before linking u, as in the original LT.
anc[u] = p;
}
for (int i = 1; i < reached; i++) {
int u = vs[i];
id[u] = semi[u] == semi[can[u]] ? vs[semi[u]] : id[can[u]];
}
return id;
}
} // namespace noya
// NOYA_DOMINATOR_TREE_HPP
#ifndef NOYA_DOMINATOR_TREE_HPP
#define NOYA_DOMINATOR_TREE_HPP 1
/// @complexity Time: O(V + E log(V + 1)) with simple link-eval.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Immediate dominators in a directed graph using Lengauer-Tarjan.
/// The root dominates itself; unreachable vertices have parent -1.
/// Loops and parallel edges are allowed; g is unchanged.
/// Requires a valid root, valid endpoints and an int-representable vertex count.
inline std::vector<int> dominator_tree(const std::vector<std::vector<int>> &g,
int rt) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
const int n = int(g.size());
assert(0 <= rt && rt < n);
for (const auto &row : g) {
for (int to : row) {
assert(0 <= to && to < n);
}
}
std::vector<int> ord(n, -1), vs, parent;
auto dfs = [&](auto &self, int u, int p) -> void {
ord[u] = int(vs.size());
vs.push_back(u);
parent.push_back(p);
for (int v : g[u]) if (ord[v] == -1) self(self, v, u);
};
dfs(dfs, rt, -1);
const int reached = int(vs.size());
std::vector<int> id(n, -1);
id[rt] = rt;
if (reached == 1) {
return id;
}
// Only reachable predecessors matter. Loops and edges into rt cannot
// change any immediate dominator, so omit them from the reverse CSR.
std::vector<std::size_t> start(std::size_t(n) + 1);
for (int u : vs) {
for (int v : g[u]) {
if (v != u && v != rt) {
++start[v];
}
}
}
for (int u = 0; u < n; ++u) {
start[u + 1] += start[u];
}
std::vector<int> pred(start.back());
for (int u : vs) {
for (int v : g[u]) {
if (v != u && v != rt) {
pred[--start[v]] = u;
}
}
}
// Semidominators use DFS numbers; all other labels use original vertices.
std::vector<int> semi = std::move(ord);
std::vector<int> lab(n), anc(n, -1), can(n, -1);
std::iota(lab.begin(), lab.end(), 0);
// Each vertex enters one bucket once, so one next pointer is sufficient.
std::vector<int> head(n, -1), next(n);
auto ev = [&](auto &self, int u) -> int {
if (anc[u] == -1) return lab[u];
int p = anc[u], best = self(self, p);
if (semi[best] < semi[lab[u]]) lab[u] = best;
if (anc[p] != -1) anc[u] = anc[p];
return lab[u];
};
for (int i = reached - 1; i >= 1; i--) {
int u = vs[i];
for (auto j = start[u]; j < start[u + 1]; ++j) {
semi[u] = std::min(semi[u], semi[ev(ev, pred[j])]);
}
int s = vs[semi[u]], p = parent[i];
next[u] = head[s];
head[s] = u;
for (int buf = head[p]; buf != -1; buf = next[buf]) {
can[buf] = ev(ev, buf);
}
head[p] = -1;
// Evaluate the parent's bucket before linking u, as in the original LT.
anc[u] = p;
}
for (int i = 1; i < reached; i++) {
int u = vs[i];
id[u] = semi[u] == semi[can[u]] ? vs[semi[u]] : id[can[u]];
}
return id;
}
} // namespace noya
#endif // NOYA_DOMINATOR_TREE_HPP
/// @complexity Time: O(V + E log(V + 1)) with simple link-eval.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Immediate dominators in a directed graph using Lengauer-Tarjan.
/// The root dominates itself; unreachable vertices have parent -1.
/// Loops and parallel edges are allowed; g is unchanged.
/// Requires a valid root, valid endpoints and an int-representable vertex count.
inline std::vector<int> dominator_tree(const std::vector<std::vector<int>> &g,
int rt) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
const int n = int(g.size());
assert(0 <= rt && rt < n);
for (const auto &row : g) {
for (int to : row) {
assert(0 <= to && to < n);
}
}
std::vector<int> ord(n, -1), vs, parent;
auto dfs = [&](auto &self, int u, int p) -> void {
ord[u] = int(vs.size());
vs.push_back(u);
parent.push_back(p);
for (int v : g[u]) if (ord[v] == -1) self(self, v, u);
};
dfs(dfs, rt, -1);
const int reached = int(vs.size());
std::vector<int> id(n, -1);
id[rt] = rt;
if (reached == 1) {
return id;
}
// Only reachable predecessors matter. Loops and edges into rt cannot
// change any immediate dominator, so omit them from the reverse CSR.
std::vector<std::size_t> start(std::size_t(n) + 1);
for (int u : vs) {
for (int v : g[u]) {
if (v != u && v != rt) {
++start[v];
}
}
}
for (int u = 0; u < n; ++u) {
start[u + 1] += start[u];
}
std::vector<int> pred(start.back());
for (int u : vs) {
for (int v : g[u]) {
if (v != u && v != rt) {
pred[--start[v]] = u;
}
}
}
// Semidominators use DFS numbers; all other labels use original vertices.
std::vector<int> semi = std::move(ord);
std::vector<int> lab(n), anc(n, -1), can(n, -1);
std::iota(lab.begin(), lab.end(), 0);
// Each vertex enters one bucket once, so one next pointer is sufficient.
std::vector<int> head(n, -1), next(n);
auto ev = [&](auto &self, int u) -> int {
if (anc[u] == -1) return lab[u];
int p = anc[u], best = self(self, p);
if (semi[best] < semi[lab[u]]) lab[u] = best;
if (anc[p] != -1) anc[u] = anc[p];
return lab[u];
};
for (int i = reached - 1; i >= 1; i--) {
int u = vs[i];
for (auto j = start[u]; j < start[u + 1]; ++j) {
semi[u] = std::min(semi[u], semi[ev(ev, pred[j])]);
}
int s = vs[semi[u]], p = parent[i];
next[u] = head[s];
head[s] = u;
for (int buf = head[p]; buf != -1; buf = next[buf]) {
can[buf] = ev(ev, buf);
}
head[p] = -1;
// Evaluate the parent's bucket before linking u, as in the original LT.
anc[u] = p;
}
for (int i = 1; i < reached; i++) {
int u = vs[i];
id[u] = semi[u] == semi[can[u]] ? vs[semi[u]] : id[can[u]];
}
return id;
}
} // namespace noya
// NOYA_DOMINATOR_TREE_HPP