library
This documentation is automatically generated by online-judge-tools/verification-helper
graph/tree/block_cut_tree.hpp
- View this file on GitHub
- Last update: 2025-04-05 12:46:42+09:00
- Include:
#include "graph/tree/block_cut_tree.hpp"
Depends on
Verified with
Code
#ifndef KK2_GRAPH_TREE_BLOCK_CUT_TREE_HPP
#define KK2_GRAPH_TREE_BLOCK_CUT_TREE_HPP 1
#include <vector>
#include "../bcc.hpp"
namespace kk2 {
template <class G> struct BlockCutTree : BCC<G> {
std::vector<int> comp_v;
std::vector<std::vector<int>> group_v;
G forest;
int off;
BlockCutTree(const G &g_) : BCC<G>(g_) { init_bct(); }
int size() const { return group_v.size(); }
bool is_articulation(int v) const { return comp_v[v] >= off; }
private:
void init_bct() {
comp_v.resize(this->n, -1);
auto bcc_v = this->get_bcc_vertices();
off = bcc_v.size();
group_v.resize(bcc_v.size() + this->articulations.size());
forest = G(group_v.size());
for (int i = 0; i < (int)this->articulations.size(); ++i) {
comp_v[this->articulations[i]] = i + off;
group_v[i + off].emplace_back(this->articulations[i]);
}
std::vector<int> buf(this->articulations.size(), -1);
for (int i = 0; i < (int)bcc_v.size(); ++i) {
for (auto &v : bcc_v[i]) {
group_v[i].emplace_back(v);
if (comp_v[v] == -1) comp_v[v] = i;
else if (buf[comp_v[v] - off] != i) {
forest.add_edge(i, comp_v[v]);
buf[comp_v[v] - off] = i;
}
}
}
if constexpr (G::static_graph) forest.build();
}
};
} // namespace kk2
#endif // KK2_GRAPH_TREE_BLOCK_CUT_TREE_HPP#line 1 "graph/tree/block_cut_tree.hpp"
#include <vector>
#line 1 "graph/bcc.hpp"
#include <functional>
#line 6 "graph/bcc.hpp"
#line 1 "graph/lowlink.hpp"
#include <algorithm>
#include <cassert>
#line 7 "graph/lowlink.hpp"
#include <type_traits>
#line 9 "graph/lowlink.hpp"
namespace kk2 {
template <class G> struct LowLink {
static_assert(!G::directed, "LowLink requires undirected graph");
int n, m;
const G &g;
std::vector<int> ord, low;
std::vector<bool> root, used_on_dfs_tree;
std::vector<int> bridges, articulations;
LowLink(const G &g_)
: n(g_.num_vertices()),
m(g_.num_edges()),
g(g_),
ord(n, -1),
low(n, -1),
root(n, false),
used_on_dfs_tree(m, false) {
init();
}
private:
// v is a child of u in DFS tree
// edge(u, v) is a bridge <=> ord[u] < low[v]
// u is an articulation point <=> (u is root and u has two or more children) or
// there exists a v which is a child of u in DFS tree and ord[u] <= low[v]
void init() {
int k = 0;
auto dfs = [&](auto self, int u, int ei = -1) -> int {
low[u] = ord[u] = k++;
bool is_articulation = false;
int count = 0;
for (auto &&e : g[u]) {
if (e.id == ei) continue;
if (ord[e.to] == -1) {
++count;
used_on_dfs_tree[e.id] = true;
low[u] = std::min(low[u], self(self, e.to, e.id));
if (ei != -1 and ord[u] <= low[e.to]) is_articulation = true;
if (ord[u] < low[e.to]) bridges.emplace_back(e.id);
}
// back edge
else if (ord[e.to] < ord[u]) {
low[u] = std::min(low[u], ord[e.to]);
}
}
if (ei == -1 and count >= 2) is_articulation = true;
if (is_articulation) articulations.emplace_back(u);
return low[u];
};
for (int u = 0; u < n; u++)
if (ord[u] == -1) {
dfs(dfs, u);
root[u] = true;
}
}
};
} // namespace kk2
#line 8 "graph/bcc.hpp"
namespace kk2 {
template <class G> struct BCC : LowLink<G> {
BCC(const G &g_) : LowLink<G>(g_) { init_bcc(); }
std::vector<std::vector<int>> group_e;
std::vector<int> comp_e;
private:
void init_bcc() {
comp_e = std::vector<int>(this->m, -1);
auto add = [&](int ei, int k) {
group_e[k].emplace_back(ei);
comp_e[ei] = k;
};
auto dfs = [&](auto self, int u, int k = -1, int ei = -1) -> void {
for (auto &e : this->g[u]) {
if (e.id == ei) continue;
if (this->used_on_dfs_tree[e.id]) {
int nk = k;
if (this->low[e.to] >= this->ord[u])
nk = group_e.size(), group_e.emplace_back();
add(e.id, nk);
self(self, e.to, nk, e.id);
}
// back edge
else if (this->ord[e.to] < this->ord[u]) {
add(e.id, k);
}
}
};
for (int u = 0; u < this->n; u++)
if (this->root[u]) { dfs(dfs, u); }
}
public:
std::vector<std::vector<int>> get_bcc_vertices() {
std::vector<bool> buf1(this->n), buf2(this->n);
std::vector<std::vector<int>> res;
res.reserve(group_e.size());
for (auto &bc : group_e) {
if (bc.empty()) continue;
int k = (int)res.size();
res.emplace_back();
for (auto &ei : bc) {
auto e = this->g.edges[ei];
int fr = e.from, to = e.to;
if (!buf2[fr]) {
res[k].emplace_back(fr);
buf2[fr] = true;
}
if (!buf2[to]) {
res[k].emplace_back(to);
buf2[to] = true;
}
buf1[fr] = buf1[to] = true;
}
for (auto &ei : bc) {
auto e = this->g.edges[ei];
int fr = e.from, to = e.to;
buf2[fr] = buf2[to] = false;
}
}
for (int i = 0; i < this->n; i++)
if (!buf1[i]) {
int k = (int)res.size();
res.emplace_back();
res[k].emplace_back(i);
}
return res;
}
};
} // namespace kk2
#line 7 "graph/tree/block_cut_tree.hpp"
namespace kk2 {
template <class G> struct BlockCutTree : BCC<G> {
std::vector<int> comp_v;
std::vector<std::vector<int>> group_v;
G forest;
int off;
BlockCutTree(const G &g_) : BCC<G>(g_) { init_bct(); }
int size() const { return group_v.size(); }
bool is_articulation(int v) const { return comp_v[v] >= off; }
private:
void init_bct() {
comp_v.resize(this->n, -1);
auto bcc_v = this->get_bcc_vertices();
off = bcc_v.size();
group_v.resize(bcc_v.size() + this->articulations.size());
forest = G(group_v.size());
for (int i = 0; i < (int)this->articulations.size(); ++i) {
comp_v[this->articulations[i]] = i + off;
group_v[i + off].emplace_back(this->articulations[i]);
}
std::vector<int> buf(this->articulations.size(), -1);
for (int i = 0; i < (int)bcc_v.size(); ++i) {
for (auto &v : bcc_v[i]) {
group_v[i].emplace_back(v);
if (comp_v[v] == -1) comp_v[v] = i;
else if (buf[comp_v[v] - off] != i) {
forest.add_edge(i, comp_v[v]);
buf[comp_v[v] - off] = i;
}
}
}
if constexpr (G::static_graph) forest.build();
}
};
} // namespace kk2