连通性问题
stripe_python · · 算法·理论
DFS 树
对图
按照 DFS 遍历顺序赋 DFS 序,记作
E-DCC
对无向图
- 若
(u,v) 是树边,对v 进行 DFS 后\text{low}_u \gets \text{low}_v 。 - 若
(u,v) 是非树边,转移\text{low}_u \gets \text{dfn}_v 。
转移是 chkmin。数组
显然,割边 / 桥必然是树边。
定理 对
理解 条件表明
将桥删去后,所有连通块构成 E-DCC,DFS 一次即可求解。
不妨设
算法实现时,注意若有重边则应记录
:::::info[P8436 代码]
const int N = 5e5 + 5;
int n, m;
vector<pair<int, int>> e[N];
int dn, dfn[N], low[N], cut[4*N];
void tarjan(int u, int f) {
dfn[u] = low[u] = ++dn;
for (auto [v, id] : e[u]) {
if (id == f) continue;
if (!dfn[v]) {
tarjan(v, id), chkmin(low[u], low[v]);
if (low[v] > dfn[u]) cut[id] = true;
} else {
chkmin(low[u], dfn[v]);
}
}
}
int cnt, bel[N];
vector<int> dcc[N];
void dfs(int u, int x) {
bel[u] = x, dcc[x].pb(u);
for (auto [v, id] : e[u])
if (!bel[v] && !cut[id]) dfs(v, x);
}
void _main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].pb(v, i), e[v].pb(u, i);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, -1);
for (int i = 1; i <= n; i++) if (!bel[i]) dfs(i, ++cnt);
cout << cnt << '\n';
for (int i = 1; i <= cnt; i++) {
cout << dcc[i].size() << ' ';
for (int u : dcc[i]) cout << u << ' ';
cout << '\n';
}
}
:::::
V-DCC
定理 非根节点
注意特判 DFS 树根是割点的情形。实现略简单一些,可以不考虑重边。
V-DCC 比 E-DCC 复杂一些,因为割点同时属于多个点双。
求解 V-DCC 需要维护一个栈,将首次访问的点入栈。若
复杂度
:::::info[P8435 代码]
const int N = 5e5 + 5;
int n, m;
vector<int> e[N];
int dn, dfn[N], low[N], cut[N];
stack<int> st;
int cnt; vector<int> dcc[N];
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++dn, st.emplace(u);
int son = 0, deg = 0;
for (int v : e[u]) if (v != u && v != fa) {
deg++;
if (!dfn[v]) {
tarjan(v, u), chkmin(low[u], low[v]);
if (low[v] >= dfn[u]) {
if (fa != -1 || ++son > 1) cut[u] = true;
cnt++; int x;
do x = st.top(), st.pop(), dcc[cnt].pb(x); while (x != v);
dcc[cnt].pb(u);
}
} else {
chkmin(low[u], dfn[v]);
}
}
if (deg == 0 && fa == -1) dcc[++cnt].pb(u);
}
void _main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].pb(v), e[v].pb(u);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, -1);
cout << cnt << '\n';
for (int i = 1; i <= cnt; i++) {
cout << dcc[i].size() << ' ';
for (int u : dcc[i]) cout << u << ' ';
cout << '\n';
}
}
:::::
Menger 定理
Menger 定理
- 使
u \leadsto v 不连通的最小割边数,等于u \leadsto v 边不交的最大路径数。 - 使
u \leadsto v 不连通的最小割点数,等于u \leadsto v 点不交的最大路径数。
本质是最大流最小割定理。边形式 Menger 定理视作
不加证明地,给出 Menger 定理的如下推论:
推论 1 对 E-DCC 内任意两点
推论 2(Robbins 定理)连通分量可定向为 SCC,当且仅当连通分量是 E-DCC。
推论 3(Whitney 定理)对 V-DCC 内任意两点
推论 4 对
推论 5 对
推论 6 对
推论 7 对
SCC
Tarjan
有向图 DFS 树形成若干森林,不同 DFS 树必然不强连通,故只要讨论一棵 DFS 树。
维护一个栈,将首次访问的节点入栈。有向图上微调
- 若
v 未访问,对v 进行 DFS 后\text{low}_u \gets \text{low}_v 。 - 若
v 已访问且v 在栈内,转移\text{low}_u \gets \text{dfn}_v 。
可以证明,若回溯前
将所有 SCC 缩成一个点,新图必然是 DAG。需要说明,Tarjan 得到的 SCC 标号是缩点的逆拓扑序。
:::::info[B3609 代码]
const int N = 1e4 + 5;
int n, m;
vector<int> e[N];
int dn, dfn[N], low[N], ins[N];
stack<int> st;
int cnt, bel[N]; vector<int> scc[N];
void tarjan(int u) {
dfn[u] = low[u] = ++dn, st.emplace(u), ins[u] = true;
for (int v : e[u]) {
if (!dfn[v]) tarjan(v), chkmin(low[u], low[v]);
else if (ins[v]) chkmin(low[u], dfn[v]);
}
if (dfn[u] != low[u]) return;
int x; cnt++;
do x = st.top(), st.pop(), ins[x] = false,
bel[x] = cnt, scc[cnt].pb(x);
while (x != u);
}
bool vis[N];
void _main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) cin >> u >> v, e[u].pb(v);
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
cout << cnt << '\n';
for (int i = 1; i <= n; i++) {
int x = bel[i];
if (vis[x]) continue;
sort(all(scc[x]));
for (int u : scc[x]) cout << u << ' ';
cout << '\n'; vis[x] = true;
}
}
:::::
Kosaraju
直接进行两次 DFS:
- 取任意点在原图上 DFS 并赋后序遍历,得到 SCC 的逆拓扑序。
- 从标号最大点开始,在反图上 DFS 得到 SCC 划分。剩余未访问节点再取标号最大点重复操作。
复杂度
- 稠密图使用 bitset 优化 DFS 做到
O\left(\dfrac{n^2}{w}\right) 。 - 优化建图问题可以不显式建图。参见 一类图论问题。
:::::info[B3609 代码]
const int N = 1e4 + 5;
int n, m;
vector<int> e[N], e1[N];
int num, cnt, vis[N], seq[N], bel[N];
vector<int> scc[N];
void dfs1(int u) {
vis[u] = true;
for (int v : e[u]) if (!vis[v]) dfs1(v);
seq[++num] = u;
}
void dfs2(int u, int x) {
bel[u] = x, scc[x].pb(u);
for (int v : e1[u]) if (!bel[v]) dfs2(v, x);
}
void _main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].pb(v), e1[v].pb(u);
}
for (int i = 1; i <= n; i++) if (!vis[i]) dfs1(i);
reverse(seq + 1, seq + n + 1);
for (int i = 1; i <= n; i++)
if (!bel[seq[i]]) dfs2(seq[i], ++cnt);
cout << cnt << '\n';
fill(vis + 1, vis + n + 1, 0);
for (int i = 1; i <= n; i++) {
int x = bel[i];
if (vis[x]) continue;
sort(all(scc[x]));
for (int u : scc[x]) cout << u << ' ';
cout << '\n'; vis[x] = true;
}
}
:::::
2-SAT
熟知
2-SAT 问题 给定
有向边
将每个变量拆成
| 方程 | 逻辑 | 建图 |
|---|---|---|
每条方程
对有向图缩 SCC,若
结论 若 2-SAT 有解,取
求解 2-SAT 的复杂度为建图 & 缩 SCC 的复杂度。
特别地,若求 2-SAT 字典序最小解,可以逐位贪心,令
圆方树
圆方树刻画了 V-DCC 缩点后的结构,将无向图必经性转化为树上问题。
我们用方点来代表一个点双,在方点下挂圆点表示 V-DCC 中的点,局部形成一个菊花。
对于广义圆方树,我们要求圆点和方点间隔连接。以 OI-Wiki 图解为例
我们有下述圆方树结构的基本性质:
- 圆点的度数等于包含该点的 V-DCC 数目。
- 方点的度数等于该 V-DCC 的大小。
- 圆点不是叶子,当且仅当该点是原图割点。
- 圆方树的总点数
\le 2n-1 。
圆方树刻画了无向图的必经性,下面给出叙述:
定理 对于圆点
刻画 E-DCC 和 V-DCC 是容易的:
- 点双:对应着每个度数
>2 的方点的邻域圆点。 - 边双:割边对应度数
=2 的方点,删去以后形成若干连通块即为边双。注意特判重边。
建立圆方树只要对 Tarjan 求点双进行微调,下面给出代码。
:::::info[代码]
int dn, cnt, dfn[N], low[N];
stack<int> st;
int add(int u, int v); // 圆方树边 (u, v)
void tarjan(int u) {
dfn[u] = low[u] = ++dn, st.emplace(u);
for (int v : e[u]) {
if (!dfn[v]) {
tarjan(v), chkmin(low[u], low[v]);
if (low[v] != dfn[u]) continue;
int x; add(u, ++cnt);
do x = st.top(), st.pop(), add(x, cnt);
while (x != v);
} else {
chkmin(low[u], dfn[v]);
}
}
}
:::::
练习
CF1325F Ehab's Last Theorem
给出一个
n 个点m 条边的连通无向图,找到一个大小为\lceil\sqrt{n}\rceil 的独立集,或者一个大小不小于\lceil\sqrt{n}\rceil 的环,输出构造。
:::::success[题解]
考虑拉出一棵 DFS 生成树,如果存在一条返祖边,其端点深度差
反之考虑按深度模
| 复杂度 |
|---|
P6954 [NEERC 2017] Connections
给定一张
n 个点m 条边的强连通有向图,保证n \ge 4 \land m>2n 。你需要保留恰好2n 条边,使图仍然强连通,输出构造。多测,
\sum m \le 10^5 ,3 秒,512 MB。
:::::success[题解]
任取一点
注意到
复杂度
:::::
CF1519E Off by One
给定
n 个点(x_i,y_i) ,每个点可以变成(x_i+1,y_i) 或(x_i,y_i+1) 。若(0,0),(x_i,y_i),(x_j,y_j) 三点共线则可以匹配i,j 并删去。求最大匹配,并输出一组方案。
:::::success[题解]
直观的想法是若
进行点边转化,将斜率视作顶点,点视作边。记
问题是
对
拉出一棵 DFS 树,自底向上贪心。设计函数 dfs(u) 返回
- 若
v 未访问,调用dfs(v)得到e' 。- 若
e' 存在,则将e 和e' 配对。 - 若
e' 不存在,则保留e 。
- 若
- 若
v 已访问,说明u\to v 是返祖边,也保留e 。
遍历结束后,将被保留的
总复杂度
:::::
CF555E Case of Computer Network
给出一个
n 个点m 条边的无向图。给定k 对节点(u_i,v_i) ,你需要将所有边定向,使得任意u_i \leadsto v_i 可达。判定是否存在可行方案。
:::::success[题解]
Robbins 定理 连通分量可定向为 SCC,当且仅当连通分量是 E-DCC。
对原图缩 E-DCC 得到一棵树。判掉
使用树上差分标记方向,若某条边同时确定为
复杂度
:::::
QOJ15449 Finances
现有
n 个人,第i 个人持有a_i 元,负数表示债务,保证\sum\limits_{i=1}^n a_i=0 。记A=\sum \limits_{i=1}^n \max(0,a_i) 。给定
m 条交易关系(u,v,c) ,表示u \leftrightarrow v 之间可以相互转账,总额度不超过c 。保证关系网连通,任意边c \ge \lceil A/2 \rceil 。求若干次转账后能否使得每人持有
0 元。多测,
\sum n ,\sum m \le 10^6 ,3 秒,1024 MB。
:::::success[题解]
注意到
边双缩点,新点权值
对
对树一次 DFS 即可判定。总复杂度
:::::
P3225 [HNOI2012] 矿场搭建
给定一个
n 个点m 条边的连通无向图。你需要设置若干关键点,使得任意一个点删掉后,其余点总能到达一个关键点。输出关键点的最少数目,以及达成此数目的方案数。保证答案
< 2^{64} 。
:::::success[题解]
考虑求出所有割点。此时对于一个大小为
- 若割点数目
>1 ,删去任意点总能连通,故无需设置特殊点; - 若割点数目
=1 ,则在除割点外的点设置特殊点即可;如果这个特殊点被删,通过割点可以到达其他特殊点。方案数为k-1 ; - 若无割点,则任选两个点作为特殊点,删去点后总能连通,方案数为
\binom{k}{2} 。
| 复杂度 |
|---|
QOJ14810 Trajan Algorithm
有错误的求割点「Trajan 算法」,问题在于返祖边转移
\text{low}_u \gets \text{low}_v 。给定一张n 个点m 条边无向图,出边顺序确定,求会被错判的所有点。多测,
\sum n, \sum m \le 10^6 ,2 秒,1024 MB。
:::::success[题解]
割点判定定理是
考察下图所示的情形:
标准 Tarjan 算法令
而 DFS 回溯时
在
结论 割点
等价表述是,
复杂度
:::::
P9697 [GDCPC 2023] Canvas
现有长为
n 的序列a_i ,初始a_i=0 。给定m 次操作(u_i,v_i,x_i,y_i) ,保证x_i,y_i \in \{1,2\} 。操作令a_{u_i} \gets x_i, a_{v_i} \gets y_i 。你可以按任意顺序执行操作,最大化
\sum \limits_{i=1}^n a_i 并输出构造。多测,
\sum n,\sum m \le 5 \times 10^5 ,3 秒,1024 MB。
:::::success[题解]
时光倒流,将覆盖操作转化为,首次操作后数值固定不变。
不难发现
不妨设
- 若原图强连通,任意选点后 DFS,则只有 DFS 树根节点为
1 ,其余点全为2 。 - 若图是 DAG,按照拓扑序操作,只有零入度点为
1 ,其余点全为2 。
对有向图进行 SCC 缩点,按缩点后拓扑序操作即可。注意零入度 SCC 的根节点尽量选择
复杂度
:::::
QOJ2214 Link Cut Digraph
维护一张
n 个点初始无边的有向图,进行m 次加边,每次操作后求出强连通点对数。
:::::success[题解]
设
对时间轴升序扫描,若
问题转化为求每条边
对分治区间上的边
- 若
f(e) \le m 且T(e) >m ,边e 不满足f(e) \ge T(e) 故直接删去。 - 若
f(e) \le m 且T(e) \le m ,边e 在左侧[l,m] 正常,在右侧(m,r] 等效为u \leftrightsquigarrow v 分量的单点。 - 若
f(e) > m 且T(e) >m ,边e 只在右侧(m,r] 可用。 - 若
f(e)>m 且T(e) \le m ,边e 对左侧不改变强连通性,故只对右侧(m,r] 有效。
每条边
注意精细实现,只遍历
总复杂度
:::::
CF1989F Simultaneous Coloring
现有一个
n \times m 的网格,你可以将一列涂黑,或者将一行涂白。每轮可以同时进行
k 次操作,代价为[k>1]k^2 。对于同时受到两类操作影响的格子,颜色可以自由选定。进行
q 次操作,给定(x,y,c) ,增加一条限制,格子(x,y) 必须涂成颜色c 。每次操作后,输出满足所有要求的最小代价。
:::::success[题解]
显然行列至多操作一次。设第
考虑用
分析可得,最优策略一定是对每个 SCC 整体操作,再按缩点后拓扑序依次操作。答案即为所有 SCC 点数平方和。
离线时间轴分治求出每条边的闭合时刻
视
:::::
P9139 [THUPC 2023 初赛] 喵了个喵 II
给定一个长为
4n 的序列,其中1\sim n 各出现4 次。你需要将其划分为两个相等的子序列,输出构造或报告无解。
:::::success[题解]
考虑问题的弱化,即
结论 无解当且仅当
1221 和 1212 是很好的例子。如果有解,则只要将
受上述讨论启发,记数值
实际上,我们只要关注前两种划分方案。设布尔变量
-
这个约束的实际意义是,对于两个导致包含关系的选择,禁止二者同选。其他情形同理。
这是一个 2-SAT 问题。对约束中的
转二维平面分析,则
可以做主席树优化建图,或者 CDQ 分治套前缀优化建图,Tarjan 求解复杂度
不过我们还有一种更聪明的手法,可以使用 Kosaraju 求 SCC,这样只要两次 DFS。考虑这篇文章中提及的技巧,假设节点
使用线段树维护左端点
注意两次 DFS 时正反图的对应关系。复杂度仍为
:::::
CF487E Tourists
给定一张
n 个点m 条边的无向连通图,点带权w_i 。进行q 次操作:
- 给定
i,x ,令w_i \gets x 。- 给定
u,v ,查询u \leadsto v 所有简单路径中,点权\min 的最小值。
:::::success[题解]
两个
建立广义圆方树,转化为单点修改,链
我们将圆点权值挂在邻域方点上,在方点处用 multiset 记最小值,只要使用普通树剖套线段树解决。复杂度
:::::
P16136 [ICPC 2018 NAIPC] Winter Festival
给定一张
n 个点m 条边的无向图。你需要将边赋一组权w(e) ,满足下列条件:
- 边权
w(e) \in \{0,1,2\} 。- 对任意简单环
C ,\sum \limits_{e \in C} w(e) \equiv 1 \pmod 2 。- 对任意点
u 的任意出边e_1,e_2 ,(w(e_1)+w(e_2)) \bmod3 \ne 1 。最小化
\sum \limits_{e \in E} w(e) 并输出,或报告无解。
:::::success[题解]
性质 有解的必要条件是
证明 设简单环
三式相加得
左式显然为偶数,矛盾。故原图必为边仙人掌。
建立原图的广义圆方树,并在圆方树上 DP。设
- 仅考虑圆点
u 子树内部。 - 所有原图边已赋权,满足约束。
- 对方点
v \in \text{son}(u) ,所有(u,v) 边颜色构成集合S 。
根据约束,合法的S 满足0,1 不共存,2 至多出现一次,从而至多6 种。下文使用集合符号表述,但注意合并集合时拒绝2 的重复。
设方点
为方便书写,定义两个辅助量,对圆点
意义是方点父亲接 1/2 条边的代价。对边仙人掌,方点必定为桥或简单环,下面讨论方点 DP。
若方点
若方点
-
设
g_{i,y,s} 表示满足下列条件的最小代价:- 仅考虑环上前
i 条边e_1 \sim e_i 。 -
-
- 仅考虑环上前
-
枚举
w(e_{i-1})=y \land w(e_i)=z ,容易列出转移g_{i,z,s+z} \gets g_{i-1,y,s} + A_{v_i}(y,z)+z -
DP 初值为
g_{0,a,a}=a 。 -
枚举
w(e_0)=a \land w(e_k)=b ,则传递h_{p,\{a,b\}} \gets g_{k,b,1} 。
初始 DP 令
总复杂度
:::::
P8456 「SWTR-8」地地铁铁
给定一张
n 个点m 条边的无向连通图,每条边染为黑色或白色。求点对(x,y) 的数目,存在简单路径x\leadsto y 有两种颜色。