G7023 [GESP202609 七级] 必经之路 题解

知识点：有向图、广度优先搜索、必经点。

解题思路

依次禁用每个节点，仍从原图所有入度0的起点BFS；若还能到达原图任一出度0的终点，则该节点不是必经点，否则计入。

为什么正确

存在避开禁用节点的起点到终点路径，恰是该节点不属于所有路线的定义；搜索完整判定是否存在这样的反例路径。

易错点

起点与终点须使用原图入度、出度定义，删除后新出现的零度点不算新的起终点。

复杂度

时间O(n(n+m))，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>g(n+1);
    vector<int>in(n+1),out(n+1),ans;
    while(m--) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        in[v]++;
        out[u]++;
    }
    for(int ban=1;ban<=n;ban++) {
        vector<int>vis(n+1),q;
        for(int u=1;u<=n;u++)if(!in[u]&&u!=ban) {
            q.push_back(u);
            vis[u]=1;
        }
        bool escape=false;
        for(int k=0;k<(int)q.size();k++) {
            int u=q[k];
            if(!out[u]) {
                escape=true;
                break;
            }
            for(int v:g[u])if(v!=ban&&!vis[v]) {
                vis[v]=1;
                q.push_back(v);
            }
        }
        if(!escape)ans.push_back(ban);
    }
    cout<<ans.size()<<"\n";
    for(int u:ans)cout<<u<<" ";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。