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