简单消除序（PEO）是弦图的充要条件；MCS通过贪心选择当前已标记邻居数最多的未标记顶点构造候选PEO，仅当输入图为弦图时结果才为真PEO，需后续验证。
什么是简单消除序，为什么MCS能生成它
简单消除序（Perfect Elimination Ordering, PEO）是弦图判定的核心。如果一个无向图存在PEO，那它就是弦图；反之亦然。MCS算法不直接验证弦图，而是构造一个候选PEO：从最后一个顶点开始，每次选当前“势”（已标记邻居数）最大的未标记顶点，标记它为序列中下一个位置。
MCS本身不保证结果一定是PEO——只有当输入图确实是弦图时，它输出的顺序才是PEO。所以实际使用中，你必须后续验证该序列是否真为PEO（即对每个顶点，其在序列中排在它前面的邻居构成一个团）。
关键点在于：MCS 是贪心策略，不回溯，也不检查边完整性；它只依赖邻接关系和标记状态。
怎么用C++实现MCS找候选消除序
标准MCS实现需要：
立即学习“C++免费学习笔记（深入）”；
- 一个优先队列（按势降序），支持动态更新
- 每个顶点的当前势（
weight），初始为0 - 标记数组
marked - 邻接表
adj（推荐用vector<vector<int>></int>）
由于C++标准库的 priority_queue 不支持减量更新，常见做法是用 set 或 multiset 存储 {-weight[v], v}（负号实现最大堆语义），插入时直接加新条目，取时跳过已标记项。
实操建议：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 初始化所有
weight[v] = 0，把每个v插入set一次 - 每次取出
set中第一个未标记顶点v，加入结果序列peo - 对每个未标记邻居
u，执行weight[u]++，并插入新键{-weight[u], u} - 用
marked[v] = true标记，不再访问
vector<int> mcs(const vector<vector<int>>& adj) {
int n = adj.size();
vector<bool> marked(n, false);
vector<int> weight(n, 0);
set<pair<int, int>> pq; // {-weight, vertex}
for (int i = 0; i < n; ++i) pq.insert({0, i});
<pre class='brush:php;toolbar:false;'>vector<int> peo;
peo.reserve(n);
while (!pq.empty()) {
auto it = pq.begin();
while (marked[it->second]) {
pq.erase(it);
it = pq.begin();
}
int v = it->second;
pq.erase(it);
marked[v] = true;
peo.push_back(v);
for (int u : adj[v]) {
if (!marked[u]) {
pq.erase({-weight[u], u});
weight[u]++;
pq.insert({-weight[u], u});
}
}
}
reverse(peo.begin(), peo.end()); // MCS构造的是逆序（最后标记的在前）
return peo;}
验证得到的序列是不是真正PEO
即使MCS跑完，也得验证：对每个顶点 v，考察它在 peo 中的位置 i，收集所有在 peo[0..i-1] 中且与 v 相邻的顶点，检查它们是否两两相邻（即构成团）。
验证复杂度是 O(n^3) 最坏，但可优化到 O(n+m)：对每个 v，用布尔数组标记其前置邻居，再遍历每个前置邻居 u，检查 u 的所有邻居中，在前置集合里的是否恰好是除 u 外全部前置邻居（即度数匹配）。
容易踩的坑：
- 没反转MCS输出——MCS自然产出的是“消除顺序的逆序”，即最后被选的顶点应最先被消除，对应PEO首元素
- 验证时忽略自环或重边（弦图定义要求简单图，输入前应去重）
- 邻接表未用无向方式建边（
adj[u].push_back(v)和adj[v].push_back(u)都要） - 验证团时用邻接矩阵查边是
O(1)，但建矩阵是O(n^2)；若稀疏图，用unordered_set存每行邻居更省空间
遇到非弦图时MCS会怎样
MCS照常运行，输出一个排列，但它不是PEO。验证阶段会失败——必存在某个 v，其前置邻居不构成团。此时可直接返回“非弦图”。
注意：MCS不能用来“修复”图或找最小弦补集，它只是判定流程中的一环。如果你需要找弦补（chordal completion），那是NP-hard问题，得换算法（如最小填充分析、启发式MCS变种等）。
最易被忽略的一点：MCS对顶点编号敏感——相同图不同编号可能导致不同输出序列，但只要图是弦图，任一MCS输出都可通过验证。别因为两次运行结果不同就怀疑实现有错。
