必经之路 题解

一、题目理解

给定一张有 (n) 个点、(m) 条边的有向图。

• 合法起点：入度为 (0) 的结点。
• 合法终点：出度为 (0) 的结点。
• 必经点：如果从任意合法起点到任意合法终点的所有路径都会经过结点 (u)，则称 (u) 为必经点。
• 注意：合法起点和合法终点本身也可以是必经点。

要求找出所有必经点，按编号从小到大输出。
如果没有必经点，只输出一行 0。

---

二、核心思路

1. 多源多汇 → 单源单汇

图中有多个合法起点和多个合法终点，直接判断“所有路径是否经过某点”比较麻烦。

我们可以添加两个虚拟结点：

• 超级源点 (S)，编号设为 (0)
• 超级汇点 (T)，编号设为 (n+1)

然后：

• 从 (S) 向每个入度为 (0) 的结点连一条有向边；
• 从每个出度为 (0) 的结点向 (T) 连一条有向边。

这样，原图中任意一条从合法起点到合法终点的路径，都对应新图中一条从 (S) 到 (T) 的路径。

问题转化为：

在新图中，哪些结点是 (S) 到 (T) 的所有路径都必须经过的？

2. 如何判断一个点是不是必经点？

一个直观的方法：删除这个点，看 (S) 还能不能到达 (T)。

• 如果删除后 (S) 无法到达 (T)，说明原来所有 (S \to T) 的路径都经过这个点，它就是必经点。
• 如果删除后 (S) 仍然可以到达 (T)，说明存在一条不经过它的路径，它不是必经点。

因为 (n \le 1000)，(m \le 2000)，我们可以对每个结点都做一次 BFS/DFS 来判断。

总时间复杂度：

[
O(n(n+m))
]

大约是 (1000 \times 3000 = 3 \times 10^6)，完全可以在 1 秒内跑完。

---

三、算法步骤

1. 读入数据，建立正向图 g，同时统计每个点的入度 in_deg 和出度 out_deg。

2. 设置超级源汇：

S = 0,\quad T = n + 1

遍历所有点 (i)：

• 若 in_deg[i] == 0，则 g[S].push_back(i)；
• 若 out_deg[i] == 0，则 g[i].push_back(T)。

3. 枚举每个点 (i)（1 到 (n)）：

   • 从 (S) 开始 BFS，标记访问过的点，但跳过结点 (i)。
   • 如果 BFS 结束后 (T) 没有被访问到，说明删除 (i) 后 (S) 到 (T) 不可达，(i) 是必经点，加入答案数组。

4. 输出答案：

   • 第一行输出必经点数量 (k)。
   • 如果 (k > 0)，第二行按从小到大输出所有必经点编号，用空格分隔。
   • 如果 (k = 0)，只输出第一行 0。

---

四、正确性证明

命题：结点 (u) 是必经点 (\iff) 在新图中删除 (u) 后，(S) 无法到达 (T)。

证明：

• 若删除 (u) 后 (S) 无法到达 (T)，说明原图中所有从合法起点到合法终点的路径都必须经过 (u)（否则可以绕过 (u) 形成一条 (S \to T) 路径），所以 (u) 是必经点。
• 若删除 (u) 后 (S) 仍能到达 (T)，则存在一条从 (S) 到 (T) 的路径不经过 (u)，对应原图中一条从合法起点到合法终点且不经过 (u) 的路径，所以 (u) 不是必经点。

证毕。

---

五、复杂度分析

• 建图：(O(n + m))
• 对每个点做一次 BFS：每次 (O(n + m))，共 (n) 次，总 (O(n(n + m)))
• 空间：邻接表 (O(n + m))，辅助数组 (O(n))

对于 (n \le 1000, m \le 2000)，时间约 (3 \times 10^6) 次操作，非常安全。

---

六、参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
vector<int> g[MAXN];          // 邻接表，包含超级源点 S=0 和超级汇点 T=n+1
int n, m;
int in_deg[MAXN], out_deg[MAXN];
int S, T;

// 检查删除结点 ban 后，S 能否到达 T
bool canReach(int ban) {
    vector<bool> vis(n + 2, false);   // 注意结点编号到 n+1
    queue<int> q;
    q.push(S);
    vis[S] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == T) return true;      // 到达 T，说明存在不经过 ban 的路径
        for (int v : g[u]) {
            if (v == ban) continue;   // 跳过被删除的结点
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    return false;                     // 无法到达 T
}

int main() {
    cin >> n >> m;
    // 初始化
    for (int i = 1; i <= n; i++) {
        in_deg[i] = out_deg[i] = 0;
        g[i].clear();
    }
    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in_deg[v]++;
        out_deg[u]++;
    }
    
    S = 0;
    T = n + 1;
    // 连接超级源点和超级汇点
    for (int i = 1; i <= n; i++) {
        if (in_deg[i] == 0) g[S].push_back(i);
        if (out_deg[i] == 0) g[i].push_back(T);
    }
    
    vector<int> ans;
    // 枚举每个结点，判断是否为必经点
    for (int i = 1; i <= n; i++) {
        if (!canReach(i)) {
            ans.push_back(i);
        }
    }
    
    // 输出结果
    cout << ans.size() << endl;
    if (!ans.empty()) {
        for (int i = 0; i < (int)ans.size(); i++) {
            if (i > 0) cout << " ";
            cout << ans[i];
        }
        cout << endl;
    }
    return 0;
}