USACO/race3

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 4 .3中的OI题目Street Race的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

• 一道基础的连通分量的图论题。这个题默认了0为起点，N为终点，如果不放心可以再读入的时候判断起点和终点，即入度为0的点为起点，出度为0的点为终点。

• 该题有两问，第一问很简单，可以尝试去掉每一个点，判断从起点到终点是否有通路，如果没有则该点为“必经点”。

• 第二问重点在于理解题意。首先可以确定第二问的解集是第一问的子集，所以我们可以第一问得出的每个点深搜，记录下可以到达的点。然后去掉该点，从起点深搜。如果不存在两次深搜皆可到达的点，就说明它是分割

---

关于第2问 【大牛表BS我......】第2问貌似不需要DFS...Floyd然后把良好图的条件判断一遍就可以了...不过时间很丑陋...

---

关于第二问 我使用的办法是深度判断，过了测试，但不知道理论上正确不？ 对原图bfs后，标记深度，对于结果1中的点bfs，如果遍历到的点深度小于起点，则不为中间点。

--菜鸟表示此方法正确

---

与方法一类似一个方法

首先，在第一次dfs的时候，先标志检查的点为红色，然后从0开始dfs,标上红色。如果这时候n点没有标上红色，则检查点为必经点。然后，第二问。。在第一问标上红色后，如果是必经点，把检查点标上黑色，从检查点开始遍历，标上黑色，如果遍历过程中没有见过红色点，最后到达了n点，则检查点是中间路口。。。。应该很容易证明。。

（线性算法）____首先bfs全图 所需的点必“按顺序”地处于最短路径上（假如不按顺序则与最短矛盾） 原图被这些点分割成许多段 对于每一个点v1 开始向后dfs直到遇到其他阶段点为止 则遍历到最靠后的阶段点v2到原先选择dfs的点v1之间的点不可能是第一问的点（存在另一条路从v1到达v2） 对于第二问 只需要在dfs的时候判断是否反向dfs到前面的阶段点v3 如果是 则v3到v1（包括v1）之间不存在第二问的点 相当于对原图进行分阶段遍历 总时间为O（n）___

看了一眼数据量... 第一个枚举+SPFA 第二个枚举+并查集

范例程序

• Pascal程序代码
• C程序代码
• C++程序代码