Cycling City | Codeforces 521E

题目链接

给定一张 \(n\) 个点 \(m\) 条边的简单无向图。

问在图中能否找到两个点,满足这两个点之间有至少三条点不相交的简单路径,有解要打印三条路径。

\(n,m \le 2 \cdot 10^5\) 不保证图连通。

考虑 \(u \rightarrow v\) 有三条点不相交的路径会是什么样子,发现有两个环相交了。

反过来,如果任意两个环都不相交,即仙人掌,那就无解。

至此,得到了有解的充要条件:不是仙人掌。

但为了便于打印路径,采用另一种方法。

\(low_u\)tarjan 算法中的定义,\(Low_u\) 表示次小值。

如果 \(Low_u = dfn_u\),则子树内的一个点到子树外的一个点至多有两条点不相交的简单路径。

于是存在满足 \(Low_u < dfn_u\) 的点 \(u\) 是有解的必要条件。

观察这张图,如果 \(lca(v,V)=u\),那么 \(u \rightarrow Low\)\(u \rightarrow v \rightarrow low \rightarrow Low\)\(u \rightarrow V \rightarrow Low\) 是三条点不相交的简单路径。

只要以 \(u\) 为根的子树中只有 \(u\) 一个点满足 \(Low_u < dfn_u\),则 \(lca(v, V) = u\)

dfs 过程中第一次找到满足 \(Low_u < dfn_u\) 的点 \(u\) 即符合上一行的条件,因为它是子树中最后判定的点。

复杂度 \(O(n)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
const int N = 2e5 + 5;
typedef vector <int> vi;
int n, m; vi G[N];
int idx, dfn[N], fa[N], ma;
struct node {
int u, fa, U, Fa;
node(int uu) { u = fa = U = Fa = uu; }
void upd(int uu, int ffa) {
if(dfn[ffa] < dfn[fa]) U = u, Fa = fa, u = uu, fa = ffa;
else if(dfn[ffa] < dfn[Fa]) U = uu, Fa = ffa;
}
} as(0);
node dfs(int u) {
dfn[u] = ++idx; node lowu(u);
for(int v : G[u]) if(!dfn[v]) {
fa[v] = u;
node lowv = dfs(v);
lowu.upd(lowv.u, lowv.fa), lowu.upd(lowv.U, lowv.Fa);
} else if(dfn[v] < dfn[u] && v ^ fa[u]) lowu.upd(u, v);
if(!ma && dfn[lowu.Fa] < dfn[u]) as = lowu, ma = u;
return lowu;
}
vi find(int s, int t) {
vi p;
while(s ^ t) p.pb(s), s = fa[s];
p.pb(t);
return p;
}
vi p;
void print() {
printf("%llu ", p.size());
for(int u : p) printf("%d ", u);
puts("");
}
int main() {
cin >> n >> m;
int u, v;
rep(i, 1, m) scanf("%d%d", &u, &v), G[u].pb(v), G[v].pb(u);
rep(i, 1, n) if(!ma && !dfn[i]) dfs(i);
if(ma) {
puts("YES");
p = find(ma, as.Fa), print();
p = find(as.U, ma), reverse(p.begin(), p.end());
p.pb(as.Fa), print();
p = find(as.Fa, as.fa); vi t = find(as.u, ma);
p.insert(p.end(), t.begin(), t.end());
reverse(p.begin(), p.end()), print();
} else puts("NO");
return 0;
}