Case of Computer Network | Codeforces 555E

题目链接

给定一张 \(n\) 个点 \(m\) 条边的无向图和 \(q\) 组有序点对 \((s_i,t_i)\)

询问是否可以给每条边定向,使得所有的 \(s_i\) 都能到达 \(t_i\)

\(n,m,q \le 2 \cdot 10^5\) 不保证图连通,可能有重边。

先假设有解,尝试求出一组解,再判定这组解合不合法。

构造解

一个经典结论:

一个边双连通分量存在一种给每条边定向的方案,使之成为强连通分量

一个强连通分量把有向边变成无向边后成为边双连通分量

对于前者直接让树边向下,反向边向上即可。

对于后者考虑一条有向边的两个端点可以相互到达,推出这条边在一个简单环上。

把图中的边双全部定向成强连通分量,接下来只需要给所有定向,以使 \(s_i\) 所在的边双能到达 \(t_i\) 所在的边双。

其实无需求边双,只需求出哪些边是桥即可,由于此题有重边,tarjan 算法应当记录上一条边而不是父亲

建出 dfs 树,对于每组 \((s_i,t_i)\),要求 \(s_i\)\(t_i\) 路径上的桥由 \(s_i\) 指向 \(t_i\)

\(s_i \rightarrow lca\) 上的边 \(+1\)\(lca \rightarrow t_i\) 上的边 \(-1\),树上差分转换为 \(s_i\)\(+1\)\(t_i\)\(-1\)\(lca\) 处不变。

一条边的最终权值如果为正,则必须向上,为负则必须向下,为 \(0\) 则都可以。

判定

检验 \(s_i \rightarrow lca\) 上的边是否全部为正,\(lca \rightarrow t_i\) 上的边是否全部为负。

\(up_u\) 表示从 \(u\) 开始只经过非桥边和权值为的桥边能到达的深度最小的结点。

\(down_u\) 表示从 \(u\) 开始只经过非桥边和权值为的桥边能到达的深度最小的结点。

如果 \(up_{s_i}\)\(down_{t_i}\) 中深度较大者是 \(s_i\)\(t_i\) 的公共祖先 \((s_i,t_i)\) 就合法,使用 dfs 序可判定。

复杂度 \(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
#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++)

using namespace std;
const int N = 2e5 + 5;
int n, m, q, idx, dfn[N], suf[N], cut[N];
vector <pair <int, int>> G[N];
int vis[N], sz[N], s[N], t[N], up[N], down[N];
int dfs(int u, int lst) {
int lowu = dfn[u] = ++idx;
for(auto [v, w] : G[u]) if(!dfn[v]) {
int lowv = dfs(v, w);
lowu = min(lowu, lowv), cut[v] = lowv > dfn[u];
} else if(w ^ lst && dfn[v] < dfn[u]) lowu = min(lowu, dfn[v]);
suf[u] = idx;
return lowu;
}
void Dfs(int u) {
vis[u] = 1;
for(auto [v, w] : G[u]) if(!vis[v]) Dfs(v), sz[u] += sz[v];
}
void DFs(int u, int fa) {
vis[u] = 1, up[u] = up[fa], down[u] = down[fa];
if(!fa || (cut[u] && sz[u] <= 0)) up[u] = u;
if(!fa || (cut[u] && sz[u] >= 0)) down[u] = u;
for(auto [v, w] : G[u]) if(!vis[v]) DFs(v, u);
}
int main() {
cin >> n >> m >> q;
int u, v;
rep(i, 1, m) {
scanf("%d%d", &u, &v);
G[u].push_back({v, ++idx}), G[v].push_back({u, idx});
}
idx = 0;
rep(i, 1, n) if(!dfn[i]) dfs(i, 0);
rep(i, 1, q) scanf("%d%d", &s[i], &t[i]), sz[s[i]]++, sz[t[i]]--;
rep(i, 1, n) if(!vis[i]) Dfs(i);
mem(vis, 0);
rep(i, 1, n) if(!vis[i]) DFs(i, 0);
rep(i, 1, q) {
int lca = dfn[up[s[i]]] > dfn[down[t[i]]] ? up[s[i]] : down[t[i]];
if(dfn[s[i]] > dfn[t[i]]) swap(s[i], t[i]);
if(dfn[s[i]] < dfn[lca] || dfn[t[i]] > suf[lca]) puts("No"), exit(0);
}
puts("Yes");
return 0;
}