chordal_graph.hpp¶
用线性时间判定弦图并返回完美消除序或无弦环；忽略自环、归一化重边，证据不唯一。采用连续邻接表、权值桶和分组邻接检查。
Complexity: Time: \(O(V + E)\). Space: \(O(V + E)\).
AC 记录：chordal_graph_recognition。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E). Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <span>
#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 graph, ignoring loops and duplicate edges.
/// ord is a vertex permutation, and is a PEO exactly when ok is true. Otherwise
/// cyc lists distinct vertices of an induced cycle, without repeating its start.
/// Certificates are noncanonical and may change with edge order. Input is unchanged.
inline chordal_graph_result
chordal_graph(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
chordal_graph_result res;
res.ord.resize(n);
if (n == 0) {
assert(es.empty());
res.ok = true;
return res;
}
std::vector<std::size_t> off(std::size_t(n) + 1);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) continue;
++off[u + 1];
++off[v + 1];
}
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
std::vector<int> to(off.back());
{
auto cursor = off;
for (auto [u, v] : es) {
if (u == v) continue;
to[cursor[u]++] = v;
to[cursor[v]++] = u;
}
}
{
// Compact duplicate neighbors in place, retaining each row's input order.
std::vector<int> seen(n, -1);
std::size_t write = 0;
for (int u = 0; u < n; ++u) {
auto begin = off[u], end = off[u + 1];
off[u] = write;
for (auto i = begin; i < end; ++i) {
int v = to[i];
if (seen[v] == u) continue;
seen[v] = u;
to[write++] = v;
}
}
off[n] = write;
to.resize(write);
}
auto adj = [&](int u) {
return std::span<const int>(to).subspan(off[u], off[u + 1] - off[u]);
};
std::vector<int> pos(n);
{
// Intrusive buckets give constant-time removal and weight increments.
// A selected vertex has weight -1; distinct-neighbor weights are < n.
std::vector<int> weight(n), head(n, -1), next(n), prev(n);
for (int u = 0; u < n; ++u) {
next[u] = u - 1;
prev[u] = u + 1 < n ? u + 1 : -1;
}
head[0] = n - 1;
int maximum = 0;
auto erase = [&](int u) {
if (prev[u] == -1) head[weight[u]] = next[u];
else next[prev[u]] = next[u];
if (next[u] != -1) prev[next[u]] = prev[u];
};
for (int i = n - 1; i >= 0; --i) {
while (head[maximum] == -1) --maximum;
int u = head[maximum];
erase(u);
res.ord[i] = u;
pos[u] = i;
weight[u] = -1;
for (int v : adj(u)) {
if (weight[v] == -1) continue;
erase(v);
++weight[v];
prev[v] = -1;
next[v] = head[weight[v]];
if (next[v] != -1) prev[next[v]] = v;
head[weight[v]] = v;
maximum = std::max(maximum, weight[v]);
}
}
}
int bad = -1, first = -1, second = -1;
{
// Group by the earliest later neighbor, then mark its adjacency once for
// all its children. This checks all PEO conditions in total linear time.
std::vector<int> head(n, -1), next(n, -1), mark(n, -1);
for (int u = 0; u < n; ++u) {
int p = -1;
for (int v : adj(u))
if (pos[v] > pos[u] && (p == -1 || pos[v] < pos[p])) p = v;
if (p != -1) {
next[u] = head[p];
head[p] = u;
}
}
for (int p = 0; p < n; ++p) {
if (head[p] == -1) continue;
for (int v : adj(p)) mark[v] = p;
for (int u = head[p]; u != -1; u = next[u]) {
if (bad != -1 && pos[u] >= pos[bad]) continue;
for (int v : adj(u)) {
if (pos[v] > pos[p] && mark[v] != p) {
bad = u;
first = p;
second = v;
break;
}
}
}
}
}
if (bad == -1) {
res.ok = true;
return res;
}
// For the first failing reverse-MCS vertex, connect the two nonadjacent
// later neighbors while excluding its other neighbors. A shortest path
// has no chords, and adding bad closes an induced cycle.
std::vector<int> pre(n, -1), queue{second};
queue.reserve(n);
pre[bad] = -2;
for (int v : adj(bad)) pre[v] = -2;
pre[first] = -1;
pre[second] = second;
for (std::size_t h = 0; h < queue.size() && pre[first] == -1; ++h) {
for (int v : adj(queue[h])) {
if (pre[v] != -1 || pos[v] <= pos[bad]) continue;
pre[v] = queue[h];
queue.push_back(v);
}
}
assert(pre[first] != -1);
res.cyc.push_back(bad);
for (int u = first; u != second; u = pre[u]) res.cyc.push_back(u);
res.cyc.push_back(second);
return res;
}
} // namespace noya
// NOYA_CHORDAL_GRAPH_HPP
#ifndef NOYA_CHORDAL_GRAPH_HPP
#define NOYA_CHORDAL_GRAPH_HPP 1
/// @complexity Time: O(V + E). Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <span>
#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 graph, ignoring loops and duplicate edges.
/// ord is a vertex permutation, and is a PEO exactly when ok is true. Otherwise
/// cyc lists distinct vertices of an induced cycle, without repeating its start.
/// Certificates are noncanonical and may change with edge order. Input is unchanged.
inline chordal_graph_result
chordal_graph(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
chordal_graph_result res;
res.ord.resize(n);
if (n == 0) {
assert(es.empty());
res.ok = true;
return res;
}
std::vector<std::size_t> off(std::size_t(n) + 1);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) continue;
++off[u + 1];
++off[v + 1];
}
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
std::vector<int> to(off.back());
{
auto cursor = off;
for (auto [u, v] : es) {
if (u == v) continue;
to[cursor[u]++] = v;
to[cursor[v]++] = u;
}
}
{
// Compact duplicate neighbors in place, retaining each row's input order.
std::vector<int> seen(n, -1);
std::size_t write = 0;
for (int u = 0; u < n; ++u) {
auto begin = off[u], end = off[u + 1];
off[u] = write;
for (auto i = begin; i < end; ++i) {
int v = to[i];
if (seen[v] == u) continue;
seen[v] = u;
to[write++] = v;
}
}
off[n] = write;
to.resize(write);
}
auto adj = [&](int u) {
return std::span<const int>(to).subspan(off[u], off[u + 1] - off[u]);
};
std::vector<int> pos(n);
{
// Intrusive buckets give constant-time removal and weight increments.
// A selected vertex has weight -1; distinct-neighbor weights are < n.
std::vector<int> weight(n), head(n, -1), next(n), prev(n);
for (int u = 0; u < n; ++u) {
next[u] = u - 1;
prev[u] = u + 1 < n ? u + 1 : -1;
}
head[0] = n - 1;
int maximum = 0;
auto erase = [&](int u) {
if (prev[u] == -1) head[weight[u]] = next[u];
else next[prev[u]] = next[u];
if (next[u] != -1) prev[next[u]] = prev[u];
};
for (int i = n - 1; i >= 0; --i) {
while (head[maximum] == -1) --maximum;
int u = head[maximum];
erase(u);
res.ord[i] = u;
pos[u] = i;
weight[u] = -1;
for (int v : adj(u)) {
if (weight[v] == -1) continue;
erase(v);
++weight[v];
prev[v] = -1;
next[v] = head[weight[v]];
if (next[v] != -1) prev[next[v]] = v;
head[weight[v]] = v;
maximum = std::max(maximum, weight[v]);
}
}
}
int bad = -1, first = -1, second = -1;
{
// Group by the earliest later neighbor, then mark its adjacency once for
// all its children. This checks all PEO conditions in total linear time.
std::vector<int> head(n, -1), next(n, -1), mark(n, -1);
for (int u = 0; u < n; ++u) {
int p = -1;
for (int v : adj(u))
if (pos[v] > pos[u] && (p == -1 || pos[v] < pos[p])) p = v;
if (p != -1) {
next[u] = head[p];
head[p] = u;
}
}
for (int p = 0; p < n; ++p) {
if (head[p] == -1) continue;
for (int v : adj(p)) mark[v] = p;
for (int u = head[p]; u != -1; u = next[u]) {
if (bad != -1 && pos[u] >= pos[bad]) continue;
for (int v : adj(u)) {
if (pos[v] > pos[p] && mark[v] != p) {
bad = u;
first = p;
second = v;
break;
}
}
}
}
}
if (bad == -1) {
res.ok = true;
return res;
}
// For the first failing reverse-MCS vertex, connect the two nonadjacent
// later neighbors while excluding its other neighbors. A shortest path
// has no chords, and adding bad closes an induced cycle.
std::vector<int> pre(n, -1), queue{second};
queue.reserve(n);
pre[bad] = -2;
for (int v : adj(bad)) pre[v] = -2;
pre[first] = -1;
pre[second] = second;
for (std::size_t h = 0; h < queue.size() && pre[first] == -1; ++h) {
for (int v : adj(queue[h])) {
if (pre[v] != -1 || pos[v] <= pos[bad]) continue;
pre[v] = queue[h];
queue.push_back(v);
}
}
assert(pre[first] != -1);
res.cyc.push_back(bad);
for (int u = first; u != second; u = pre[u]) res.cyc.push_back(u);
res.cyc.push_back(second);
return res;
}
} // namespace noya
#endif // NOYA_CHORDAL_GRAPH_HPP
/// @complexity Time: O(V + E). Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <span>
#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 graph, ignoring loops and duplicate edges.
/// ord is a vertex permutation, and is a PEO exactly when ok is true. Otherwise
/// cyc lists distinct vertices of an induced cycle, without repeating its start.
/// Certificates are noncanonical and may change with edge order. Input is unchanged.
inline chordal_graph_result
chordal_graph(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
chordal_graph_result res;
res.ord.resize(n);
if (n == 0) {
assert(es.empty());
res.ok = true;
return res;
}
std::vector<std::size_t> off(std::size_t(n) + 1);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) continue;
++off[u + 1];
++off[v + 1];
}
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
std::vector<int> to(off.back());
{
auto cursor = off;
for (auto [u, v] : es) {
if (u == v) continue;
to[cursor[u]++] = v;
to[cursor[v]++] = u;
}
}
{
// Compact duplicate neighbors in place, retaining each row's input order.
std::vector<int> seen(n, -1);
std::size_t write = 0;
for (int u = 0; u < n; ++u) {
auto begin = off[u], end = off[u + 1];
off[u] = write;
for (auto i = begin; i < end; ++i) {
int v = to[i];
if (seen[v] == u) continue;
seen[v] = u;
to[write++] = v;
}
}
off[n] = write;
to.resize(write);
}
auto adj = [&](int u) {
return std::span<const int>(to).subspan(off[u], off[u + 1] - off[u]);
};
std::vector<int> pos(n);
{
// Intrusive buckets give constant-time removal and weight increments.
// A selected vertex has weight -1; distinct-neighbor weights are < n.
std::vector<int> weight(n), head(n, -1), next(n), prev(n);
for (int u = 0; u < n; ++u) {
next[u] = u - 1;
prev[u] = u + 1 < n ? u + 1 : -1;
}
head[0] = n - 1;
int maximum = 0;
auto erase = [&](int u) {
if (prev[u] == -1) head[weight[u]] = next[u];
else next[prev[u]] = next[u];
if (next[u] != -1) prev[next[u]] = prev[u];
};
for (int i = n - 1; i >= 0; --i) {
while (head[maximum] == -1) --maximum;
int u = head[maximum];
erase(u);
res.ord[i] = u;
pos[u] = i;
weight[u] = -1;
for (int v : adj(u)) {
if (weight[v] == -1) continue;
erase(v);
++weight[v];
prev[v] = -1;
next[v] = head[weight[v]];
if (next[v] != -1) prev[next[v]] = v;
head[weight[v]] = v;
maximum = std::max(maximum, weight[v]);
}
}
}
int bad = -1, first = -1, second = -1;
{
// Group by the earliest later neighbor, then mark its adjacency once for
// all its children. This checks all PEO conditions in total linear time.
std::vector<int> head(n, -1), next(n, -1), mark(n, -1);
for (int u = 0; u < n; ++u) {
int p = -1;
for (int v : adj(u))
if (pos[v] > pos[u] && (p == -1 || pos[v] < pos[p])) p = v;
if (p != -1) {
next[u] = head[p];
head[p] = u;
}
}
for (int p = 0; p < n; ++p) {
if (head[p] == -1) continue;
for (int v : adj(p)) mark[v] = p;
for (int u = head[p]; u != -1; u = next[u]) {
if (bad != -1 && pos[u] >= pos[bad]) continue;
for (int v : adj(u)) {
if (pos[v] > pos[p] && mark[v] != p) {
bad = u;
first = p;
second = v;
break;
}
}
}
}
}
if (bad == -1) {
res.ok = true;
return res;
}
// For the first failing reverse-MCS vertex, connect the two nonadjacent
// later neighbors while excluding its other neighbors. A shortest path
// has no chords, and adding bad closes an induced cycle.
std::vector<int> pre(n, -1), queue{second};
queue.reserve(n);
pre[bad] = -2;
for (int v : adj(bad)) pre[v] = -2;
pre[first] = -1;
pre[second] = second;
for (std::size_t h = 0; h < queue.size() && pre[first] == -1; ++h) {
for (int v : adj(queue[h])) {
if (pre[v] != -1 || pos[v] <= pos[bad]) continue;
pre[v] = queue[h];
queue.push_back(v);
}
}
assert(pre[first] != -1);
res.cyc.push_back(bad);
for (int u = first; u != second; u = pre[u]) res.cyc.push_back(u);
res.cyc.push_back(second);
return res;
}
} // namespace noya
// NOYA_CHORDAL_GRAPH_HPP