CF521E Cycling City 题解

Description

• 给定一张 \(n\) 个点 \(m\) 条边的无向简单图。
• 问图中能否找到两个点，满足这两个点之间有至少三条完全不相交的简单路径。
• \(n,m \le 2 \times 10^5\)，图不保证连通。

Solution

容易发现有解地充要条件是存在两个环有边交，考虑在 dfs 树上做这件事。

注意到非树边一定不会成为边交，所以边交一定为树边。

那么对于每个边维护一个数组，表示覆盖这个边地环，然后每次找到一个非树边 \((u,v)\) 并把 \(u\to v\) 路径上的边添加上 \((u,v)\)，如果跳的过程找到了交就输出答案。

考虑如何输出方案，假设是 \((u_1,v_1)\) 和 \((u_2,v_2)\) 这两个非树边对应路径的交，不妨设 \(dep_{u_1}<dep_{v_1},dep_{u_2}<dep_{v_2},dep_{v_2}<dep_{v_1}\)，则可构造出这样三条路径：

1. \(LCA(u_1,u_2)\to v_2\)
2. \(LCA(u_1,u_2)\to u_1\to v_1\to v_2\)
3. \(LCA(u_1,u_2)\to u_2\to v_2\)

由于每个边不会被覆盖超过 \(2\) 次，所以求边交和 LCA 都暴力跳即可。

时间复杂度：\(O(n+m)\)。

Code