chordal_graph.hpp¶
判定图是否为弦图，并给出完美消除序或无弦环证据；适合利用弦图结构做着色或团问题。
Complexity: Time: O((V + E) log V) with the priority-queue MCS implementation. Space: O(V + E).
AC 记录：chordal_graph_recognition。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((V + E) log V) with the priority-queue MCS implementation.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
/// @brief Chordality certificate: a perfect-elimination ordering, or an
/// induced cycle of length at least four when the graph is not chordal.
struct chordal_graph_result {
bool ok = false;
std::vector<int> ord;
std::vector<int> cyc;
};
/// @brief Recognize an undirected simple graph in O(n+m) expected practical
/// time using maximum cardinality search and return a certificate.
inline chordal_graph_result
chordal_graph(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
g[a].push_back(b);
g[b].push_back(a);
}
}
for (auto &adj : g) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
std::priority_queue<std::pair<int, int>> q;
std::vector<int> w(n), sel(n);
for (int u = 0; u < n; u++) {
q.emplace(0, u);
}
std::vector<int> or1;
or1.reserve(n);
while (!q.empty()) {
auto [cw, u] = q.top();
q.pop();
if (sel[u] || cw != w[u]) {
continue;
}
sel[u] = true;
or1.push_back(u);
for (int nxt : g[u]) {
if (!sel[nxt]) {
q.emplace(++w[nxt], nxt);
}
}
}
chordal_graph_result res;
res.ord.assign(or1.rbegin(), or1.rend());
std::vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[res.ord[i]] = i;
}
for (int i = 0; i < n; i++) {
int u = res.ord[i];
int fa = -1;
for (int nxt : g[u]) {
if (pos[nxt] > i && (fa == -1 || pos[nxt] < pos[fa])) {
fa = nxt;
}
}
if (fa == -1) {
continue;
}
for (int nxt : g[u]) {
if (pos[nxt] <= i || nxt == fa ||
std::binary_search(g[fa].begin(), g[fa].end(), nxt)) {
continue;
}
std::vector<int> pre(n, -1);
std::queue<int> bfs;
pre[nxt] = nxt;
bfs.push(nxt);
while (!bfs.empty() && pre[fa] == -1) {
int cur = bfs.front();
bfs.pop();
for (int can : g[cur]) {
if (can == u || pos[can] <= i || pre[can] != -1) {
continue;
}
if (can != fa && std::binary_search(g[u].begin(), g[u].end(), can)) {
continue;
}
pre[can] = cur;
bfs.push(can);
}
}
if (pre[fa] != -1) {
res.cyc = {u, nxt};
std::vector<int> pth;
for (int cur = fa; cur != nxt; cur = pre[cur]) {
pth.push_back(cur);
}
std::reverse(pth.begin(), pth.end());
res.cyc.insert(res.cyc.end(), pth.begin(), pth.end());
}
return res;
}
}
res.ok = true;
return res;
}
} // namespace noya
#ifndef NOYA_CHORDAL_GRAPH_HPP
#define NOYA_CHORDAL_GRAPH_HPP 1
/// @complexity Time: O((V + E) log V) with the priority-queue MCS implementation.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
/// @brief Chordality certificate: a perfect-elimination ordering, or an
/// induced cycle of length at least four when the graph is not chordal.
struct chordal_graph_result {
bool ok = false;
std::vector<int> ord;
std::vector<int> cyc;
};
/// @brief Recognize an undirected simple graph in O(n+m) expected practical
/// time using maximum cardinality search and return a certificate.
inline chordal_graph_result
chordal_graph(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
g[a].push_back(b);
g[b].push_back(a);
}
}
for (auto &adj : g) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
std::priority_queue<std::pair<int, int>> q;
std::vector<int> w(n), sel(n);
for (int u = 0; u < n; u++) {
q.emplace(0, u);
}
std::vector<int> or1;
or1.reserve(n);
while (!q.empty()) {
auto [cw, u] = q.top();
q.pop();
if (sel[u] || cw != w[u]) {
continue;
}
sel[u] = true;
or1.push_back(u);
for (int nxt : g[u]) {
if (!sel[nxt]) {
q.emplace(++w[nxt], nxt);
}
}
}
chordal_graph_result res;
res.ord.assign(or1.rbegin(), or1.rend());
std::vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[res.ord[i]] = i;
}
for (int i = 0; i < n; i++) {
int u = res.ord[i];
int fa = -1;
for (int nxt : g[u]) {
if (pos[nxt] > i && (fa == -1 || pos[nxt] < pos[fa])) {
fa = nxt;
}
}
if (fa == -1) {
continue;
}
for (int nxt : g[u]) {
if (pos[nxt] <= i || nxt == fa ||
std::binary_search(g[fa].begin(), g[fa].end(), nxt)) {
continue;
}
std::vector<int> pre(n, -1);
std::queue<int> bfs;
pre[nxt] = nxt;
bfs.push(nxt);
while (!bfs.empty() && pre[fa] == -1) {
int cur = bfs.front();
bfs.pop();
for (int can : g[cur]) {
if (can == u || pos[can] <= i || pre[can] != -1) {
continue;
}
if (can != fa && std::binary_search(g[u].begin(), g[u].end(), can)) {
continue;
}
pre[can] = cur;
bfs.push(can);
}
}
if (pre[fa] != -1) {
res.cyc = {u, nxt};
std::vector<int> pth;
for (int cur = fa; cur != nxt; cur = pre[cur]) {
pth.push_back(cur);
}
std::reverse(pth.begin(), pth.end());
res.cyc.insert(res.cyc.end(), pth.begin(), pth.end());
}
return res;
}
}
res.ok = true;
return res;
}
} // namespace noya
#endif // NOYA_CHORDAL_GRAPH_HPP
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O((V + E) log V) with the priority-queue MCS implementation.
/// Space: O(V + E).
namespace noya {
/// @brief Chordality certificate: a perfect-elimination ordering, or an
/// induced cycle of length at least four when the graph is not chordal.
struct chordal_graph_result {
bool ok = false;
std::vector<int> ord;
std::vector<int> cyc;
};
/// @brief Recognize an undirected simple graph in O(n+m) expected practical
/// time using maximum cardinality search and return a certificate.
inline chordal_graph_result
chordal_graph(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
g[a].push_back(b);
g[b].push_back(a);
}
}
for (auto &adj : g) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
std::priority_queue<std::pair<int, int>> q;
std::vector<int> w(n), sel(n);
for (int u = 0; u < n; u++) {
q.emplace(0, u);
}
std::vector<int> or1;
or1.reserve(n);
while (!q.empty()) {
auto [cw, u] = q.top();
q.pop();
if (sel[u] || cw != w[u]) {
continue;
}
sel[u] = true;
or1.push_back(u);
for (int nxt : g[u]) {
if (!sel[nxt]) {
q.emplace(++w[nxt], nxt);
}
}
}
chordal_graph_result res;
res.ord.assign(or1.rbegin(), or1.rend());
std::vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[res.ord[i]] = i;
}
for (int i = 0; i < n; i++) {
int u = res.ord[i];
int fa = -1;
for (int nxt : g[u]) {
if (pos[nxt] > i && (fa == -1 || pos[nxt] < pos[fa])) {
fa = nxt;
}
}
if (fa == -1) {
continue;
}
for (int nxt : g[u]) {
if (pos[nxt] <= i || nxt == fa ||
std::binary_search(g[fa].begin(), g[fa].end(), nxt)) {
continue;
}
std::vector<int> pre(n, -1);
std::queue<int> bfs;
pre[nxt] = nxt;
bfs.push(nxt);
while (!bfs.empty() && pre[fa] == -1) {
int cur = bfs.front();
bfs.pop();
for (int can : g[cur]) {
if (can == u || pos[can] <= i || pre[can] != -1) {
continue;
}
if (can != fa && std::binary_search(g[u].begin(), g[u].end(), can)) {
continue;
}
pre[can] = cur;
bfs.push(can);
}
}
if (pre[fa] != -1) {
res.cyc = {u, nxt};
std::vector<int> pth;
for (int cur = fa; cur != nxt; cur = pre[cur]) {
pth.push_back(cur);
}
std::reverse(pth.begin(), pth.end());
res.cyc.insert(res.cyc.end(), pth.begin(), pth.end());
}
return res;
}
}
res.ok = true;
return res;
}
} // namespace noya