Cycling
CF521E Cycling City
是一个比较无脑的算法 首先建点双,对每个点双考虑,发现点双无解当且仅当是一个环,耳分解一下非常好证明 然后只需要找到两个端点满足有三条路径即可,发现 \(\text{K4}\) 一定有解,于是缩一下广义串并联图,把缩剩下的两个点拿出来当端点跑三遍 bfs 就做完了,感觉连通性相关的图论题目每次就这些 ......
CF521E. Cycling City
套路的,先随便找这张图的一棵生成树,原条件等价于存在一条路径同时被两条非树边覆盖。 直接枚举非树边进行覆盖,发现如果只要有一条树边的覆盖次数达到了 2 就可以退出了。因此,我们选取这张图的 dfs 树作为我们的生成树。 这样做有一个很好的性质:非树边只会是返租边或是前向边。由于这是一张无向图,前向边 ......