dominator_tree.hpp¶
求流程图中每个点的直接支配点；适合判断从源点到目标的所有路径必须经过哪些点。
Complexity: Time: O((V + E) log V) with the implemented link-eval structure. Space: O(V + E).
AC 记录：dominatortree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((V + E) log V) with the implemented link-eval structure.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Immediate dominators in a directed graph using Lengauer-Tarjan.
/// The root dominates itself; unreachable vertices have parent -1.
inline std::vector<int> dominator_tree(const std::vector<std::vector<int>> &g,
int rt) {
const int n = int(g.size());
assert(0 <= rt && rt < n);
std::vector<std::vector<int>> rg(n);
for (int u = 0; u < n; u++) {
for (int to : g[u]) {
assert(0 <= to && to < n);
rg[to].push_back(u);
}
}
std::vector<int> ord(n, -1), fa(n, -1), ptr(n);
std::vector<int> vs = {rt};
std::vector<int> stk = {rt};
ord[rt] = 0;
while (!stk.empty()) {
int u = stk.back();
if (ptr[u] == int(g[u].size())) {
stk.pop_back();
continue;
}
int to = g[u][ptr[u]++];
if (ord[to] == -1) {
fa[to] = u;
ord[to] = int(vs.size());
vs.push_back(to);
stk.push_back(to);
}
}
std::vector<int> sdo(n), lab(n), anc(n, -1), can(n, -1);
std::iota(sdo.begin(), sdo.end(), 0);
std::iota(lab.begin(), lab.end(), 0);
std::vector<std::vector<int>> bkt(n);
std::vector<int> st1;
st1.reserve(vs.size());
auto ev = [&](int s) {
st1.clear();
int u = s;
while (anc[u] != -1) {
st1.push_back(u);
u = anc[u];
}
for (auto it = st1.rbegin(); it != st1.rend(); ++it) {
int cur = *it;
int up = anc[cur];
if (ord[sdo[lab[up]]] < ord[sdo[lab[cur]]]) {
lab[cur] = lab[up];
}
anc[cur] = u;
}
return lab[s];
};
for (int i = int(vs.size()) - 1; i >= 1; i--) {
int u = vs[i];
for (int v : rg[u]) {
if (ord[v] == -1) {
continue;
}
int bst = ev(v);
if (ord[sdo[bst]] < ord[sdo[u]]) {
sdo[u] = sdo[bst];
}
}
bkt[sdo[u]].push_back(u);
for (int buf : bkt[fa[u]]) {
can[buf] = ev(buf);
}
bkt[fa[u]].clear();
anc[u] = fa[u];
}
std::vector<int> id(n, -1);
id[rt] = rt;
for (int i = 1; i < int(vs.size()); i++) {
int u = vs[i];
id[u] = sdo[u] == sdo[can[u]] ? sdo[u] : id[can[u]];
}
return id;
}
} // namespace noya
#ifndef NOYA_DOMINATOR_TREE_HPP
#define NOYA_DOMINATOR_TREE_HPP 1
/// @complexity Time: O((V + E) log V) with the implemented link-eval structure.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Immediate dominators in a directed graph using Lengauer-Tarjan.
/// The root dominates itself; unreachable vertices have parent -1.
inline std::vector<int> dominator_tree(const std::vector<std::vector<int>> &g,
int rt) {
const int n = int(g.size());
assert(0 <= rt && rt < n);
std::vector<std::vector<int>> rg(n);
for (int u = 0; u < n; u++) {
for (int to : g[u]) {
assert(0 <= to && to < n);
rg[to].push_back(u);
}
}
std::vector<int> ord(n, -1), fa(n, -1), ptr(n);
std::vector<int> vs = {rt};
std::vector<int> stk = {rt};
ord[rt] = 0;
while (!stk.empty()) {
int u = stk.back();
if (ptr[u] == int(g[u].size())) {
stk.pop_back();
continue;
}
int to = g[u][ptr[u]++];
if (ord[to] == -1) {
fa[to] = u;
ord[to] = int(vs.size());
vs.push_back(to);
stk.push_back(to);
}
}
std::vector<int> sdo(n), lab(n), anc(n, -1), can(n, -1);
std::iota(sdo.begin(), sdo.end(), 0);
std::iota(lab.begin(), lab.end(), 0);
std::vector<std::vector<int>> bkt(n);
std::vector<int> st1;
st1.reserve(vs.size());
auto ev = [&](int s) {
st1.clear();
int u = s;
while (anc[u] != -1) {
st1.push_back(u);
u = anc[u];
}
for (auto it = st1.rbegin(); it != st1.rend(); ++it) {
int cur = *it;
int up = anc[cur];
if (ord[sdo[lab[up]]] < ord[sdo[lab[cur]]]) {
lab[cur] = lab[up];
}
anc[cur] = u;
}
return lab[s];
};
for (int i = int(vs.size()) - 1; i >= 1; i--) {
int u = vs[i];
for (int v : rg[u]) {
if (ord[v] == -1) {
continue;
}
int bst = ev(v);
if (ord[sdo[bst]] < ord[sdo[u]]) {
sdo[u] = sdo[bst];
}
}
bkt[sdo[u]].push_back(u);
for (int buf : bkt[fa[u]]) {
can[buf] = ev(buf);
}
bkt[fa[u]].clear();
anc[u] = fa[u];
}
std::vector<int> id(n, -1);
id[rt] = rt;
for (int i = 1; i < int(vs.size()); i++) {
int u = vs[i];
id[u] = sdo[u] == sdo[can[u]] ? sdo[u] : id[can[u]];
}
return id;
}
} // namespace noya
#endif // NOYA_DOMINATOR_TREE_HPP
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
/// @complexity Time: O((V + E) log V) with the implemented link-eval structure.
/// Space: O(V + E).
namespace noya {
/// @brief Immediate dominators in a directed graph using Lengauer-Tarjan.
/// The root dominates itself; unreachable vertices have parent -1.
inline std::vector<int> dominator_tree(const std::vector<std::vector<int>> &g,
int rt) {
const int n = int(g.size());
assert(0 <= rt && rt < n);
std::vector<std::vector<int>> rg(n);
for (int u = 0; u < n; u++) {
for (int to : g[u]) {
assert(0 <= to && to < n);
rg[to].push_back(u);
}
}
std::vector<int> ord(n, -1), fa(n, -1), ptr(n);
std::vector<int> vs = {rt};
std::vector<int> stk = {rt};
ord[rt] = 0;
while (!stk.empty()) {
int u = stk.back();
if (ptr[u] == int(g[u].size())) {
stk.pop_back();
continue;
}
int to = g[u][ptr[u]++];
if (ord[to] == -1) {
fa[to] = u;
ord[to] = int(vs.size());
vs.push_back(to);
stk.push_back(to);
}
}
std::vector<int> sdo(n), lab(n), anc(n, -1), can(n, -1);
std::iota(sdo.begin(), sdo.end(), 0);
std::iota(lab.begin(), lab.end(), 0);
std::vector<std::vector<int>> bkt(n);
std::vector<int> st1;
st1.reserve(vs.size());
auto ev = [&](int s) {
st1.clear();
int u = s;
while (anc[u] != -1) {
st1.push_back(u);
u = anc[u];
}
for (auto it = st1.rbegin(); it != st1.rend(); ++it) {
int cur = *it;
int up = anc[cur];
if (ord[sdo[lab[up]]] < ord[sdo[lab[cur]]]) {
lab[cur] = lab[up];
}
anc[cur] = u;
}
return lab[s];
};
for (int i = int(vs.size()) - 1; i >= 1; i--) {
int u = vs[i];
for (int v : rg[u]) {
if (ord[v] == -1) {
continue;
}
int bst = ev(v);
if (ord[sdo[bst]] < ord[sdo[u]]) {
sdo[u] = sdo[bst];
}
}
bkt[sdo[u]].push_back(u);
for (int buf : bkt[fa[u]]) {
can[buf] = ev(buf);
}
bkt[fa[u]].clear();
anc[u] = fa[u];
}
std::vector<int> id(n, -1);
id[rt] = rt;
for (int i = 1; i < int(vs.size()); i++) {
int u = vs[i];
id[u] = sdo[u] == sdo[can[u]] ? sdo[u] : id[can[u]];
}
return id;
}
} // namespace noya