CodeForces Round 898 (div 4) H题解析

 

 
CodeForces Round 898 (div 4)
H. Mad  City

                                                    
大致思路     

• 对于有n条边和n个点，说明这个图里面只有一个环
  
• 并且两人同时开始和结束移动，所以可以得到当Valeriu进入到这个图里面的唯一的环里面时，Marcel就无法再抓到他，我们可以把离Valeriu最近的入环点叫做KeyPoint，所以我们就需要考虑Valeriu是否能在Marcel赶到KeyPoint之前赶到KeyPoint。
  
• 所以找到入环点是这道题的切入点，找到入环点，我们就可以通过dfs暴搜来得出他们和入环点的距离来，通过比较来得出是否能够逃离。
  

Key：入环点的寻找

思路来源于洛谷的_Ink大佬
方法是通过拓扑，因为在拓扑的过程中，会一步步去删点删边，最后只剩下一个环。因为是要找离逃离者最近的入环点，所以我们可以把一开始的KeyPoint设为b点，即要逃离者所在地点，当 Keypoint 所在的点将被删时，由拓扑排序的特性，此时仅有一条边与其相连，所以我们可以在删这个点时顺势把KeyPoint 值更新到与被删点相连的那个点上。
由于拓扑排序不会删掉环上的点，所以当 KeyPoint 值不停更新，直到更新到环上的点时就不再发生变化。此时，KeyPoint 值就是我们想要的那个点的编号了。
这道题的图为无向图，所以拓扑过程中的删点删边条件应该为入度为1，这样环上的点就永远不会被删除。
完整代码

[code]#include using namespace std;const int N = 200060, M = N > n >> a >> b;    init();    keypoint = b;    for(int i=1;i> u >> v;        add(u, v);        add(v, u);        to++;        to[v]++;//因为是双向道路，所以两个点的入度都+1    }    for (int i = 1; i = 2 && a != b)//如果一开始b就在环上，而且a没有和b在同一栋大楼，就说明可以无期限逃    {        cout