C++弦图判定怎么用MCS最大势算法找简单消除序-C++-PHP中文网

简单消除序（peo）是弦图的充要条件；mcs通过贪心选择当前已标记邻居数最多的未标记顶点构造候选peo，仅当输入图为弦图时结果才为真peo，需后续验证。

c++弦图判定怎么用mcs最大势算法找简单消除序

什么是简单消除序，为什么MCS能生成它

简单消除序（Perfect Elimination Ordering, PEO）是弦图判定的核心。如果一个无向图存在PEO，那它就是弦图；反之亦然。MCS算法不直接验证弦图，而是构造一个候选PEO：从最后一个顶点开始，每次选当前“势”（已标记邻居数）最大的未标记顶点，标记它为序列中下一个位置。

MCS本身不保证结果一定是PEO——只有当输入图确实是弦图时，它输出的顺序才是PEO。所以实际使用中，你必须后续验证该序列是否真为PEO（即对每个顶点，其在序列中排在它前面的邻居构成一个团）。

关键点在于：MCS 是贪心策略，不回溯，也不检查边完整性；它只依赖邻接关系和标记状态。

怎么用C++实现MCS找候选消除序

标准MCS实现需要：

一个优先队列（按势降序），支持动态更新
每个顶点的当前势（weight），初始为0
标记数组 marked
邻接表 adj（推荐用 vector<vector>></vector>）

由于C++标准库的 priority_queue 不支持减量更新，常见做法是用 set 或 multiset 存储 {-weight[v], v}（负号实现最大堆语义），插入时直接加新条目，取时跳过已标记项。

实操建议：

初始化所有 weight[v] = 0，把每个 v 插入 set 一次
每次取出 set 中第一个未标记顶点 v，加入结果序列 peo
对每个未标记邻居 u，执行 weight[u]++，并插入新键 {-weight[u], u}
用 marked[v] = true 标记，不再访问

vector<int> mcs(const vector<vector>>& adj) {
    int n = adj.size();
    vector<bool> marked(n, false);
    vector<int> weight(n, 0);
    set<pair int>> pq; // {-weight, vertex}
    for (int i = 0; i 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;</int></pair></int></bool></vector></int>

}