必经之路 题解
一、题目理解
给定一张有 (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. 设置超级源汇：
遍历所有点 (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) 次操作，非常安全。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、参考代码
