更佳的阅读体验：2023 国庆集训 Day 6A 笔记，本文同步发表于 洛谷博客。
以下内容为个人总结，如有错误或您有不同见解，欢迎指出。
割点 / 割边
在无向图中讨论。
删掉这个点 / 边，图变得不连通。
Tarjan 求割点
- 随便找个根节点，跑 DFS，记录 DFS 访问的时间戳 $dfn$。
- 对于根节点，我们判断其是否是割点，只需判断是否有大于 $1$ 个子树。
考虑非根节点 ：
- 考虑非树边长什么样子：一定是从祖先到子孙。
- 那么假设 $x$ 不是割点，那么子树内的每个点都能到 $x$ 的上面部分。
- 设 $low[x]$ 表示 $x$ 子树内，通过非树边走到的最浅是哪里。
- 如果存在 $x$ 的儿子 $y$ 满足 $low[y] \ge dfn[x]$，那么 $x$ 就是割点。
int dfn[N], low[N], cut[N], tmp, num, cnt, rt;
void dfs(int x, int fa) {
dfn[x] = low[x] = ++num;
for (int i = h[x]; i; i = ne[i]) {
int y = to[i];
if (y == fa) continue;
if (!dfn[y]) {
dfs(y, i ^ 1), low[x] = min(low[x], low[y]);
if (x != rt && low[y] >= dfn[x]) cut[x] = 1;
if (x == rt) tmp++;
} else low[x] = min(low[x], dfn[y]);
}
}缩点
stk[++st] = u;
for (int i = point[u]; i != -1; i = edge[i].nxt) {
int v = edge[i].v;
if (!dfn[v]) {
Tarjan(v);
low[u] = min (low[u], low[v]);
// 因为v在u的子树内，所以low[v]可以用于更新low[u]
if (low[v] >= dfn[u]) { // 子树中没有可以连到父亲上面的边
cut[u] = 1;
dccn++;
dcc[dccn].clear();
dcc[dccn].push_back(u); // u是割点，可能包含在多个点双中，不能弹出
while (true) {
int w = stk[st];
dcc[dccn].push_back(w);
st--;
if (w == v) // 做到子树全部弹出为止，不然v的兄弟也会被弹出
break;
}
}
}
}Tarjan 求割边
void tarjan(int x, int fa) {
low[x] = dfn[x] = ++num;
vis[x] = true, st[++top] = x;
int cnt = 0;
for (int i = h[x]; i; i = ne[i]) {
int y = to[i];
if (y == fa && (++cnt) < 2) continue;
if (!dfn[y]) tarjan(y, x), low[x] = min(low[x], low[y]);
else low[x] = min(low[x], dfn[y]);
} if (dfn[x] == low[x] && ++sc)
while (z = st[top--]) {
col[z] = sc, vis[z] = false;
if (z == x) break;
}
}强连通分量
在有向图中，如果两个点 $u$，$v$ 满足同时存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的路径，则称两个点强连通。
如果有向图任意两个点强连通，则称为强连通图。有向图的极大强连通子图称为强连通分量。
注意到强连通关系是传递的，所以有向图可以划分为若干不交的强连通分量。
在有向图的 DFS 树中，有 树边、非树边（没用）、返祖边（有用） 和 横叉边（部分有用） 的四种边。
- DFS 到 x 时，我们用栈维护 $x$ 的每个祖先目前的强连通分量。
遍历所有 $x$ 的边 $(x, y)$：
- 如果 $y$ 未被遍历过，则 $dfs(y)$。
- 如果 $y$ 被遍历过，如果 $y$ 在某个祖先的强连通分量中，则形成了环，将若干连通分量合并，否则不做更新。
- 合并操作可以通过记录 $low$ 数组实现。
int sta[N], num;
bool vis[N];
void tarjan(int x) {
low[x] = dfn[x] = ++num;
sta[++top] = x, vis[x] = true;
for (int i = h[x]; i; i = ne[i]) {
int y = to[i];
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (vis[y]) low[x] = min(low[x], low[y]);
} if (dfn[x] == low[x]) {
int y;
while (y = sta[top--]) {
sd[y] = x;
vis[y] = false;
if (x == y) break;
w[x] += w[y];
}
}
}洛谷 P3469 - [POI2008] BLO-Blockade
- 魔改一下 Tarjan 求割点的过程。
- 得到 $sum - \sum_{low[y] \ge dfn[x]} si[y]$，$ans[x] = (n - sum - 1) \times (sum + 1) + \sum_{low[y] \ge dfn[x]} si[y](n - si[y])$。
洛谷 P1407 - [国家集训队] 稳定婚姻
- 婚姻让女方向男方连边，旧情让男方向女方连边。不安全的婚姻说明出现了环，也就是在一个连通分量内。
- 所以跑 Tarjan，一对夫妻在强连通分量里面说明不安全。
UOJ 67 - 新年的毒瘤
只需满足两个条件：
- 删掉的点不能是割点。
- 删掉这个点以后满足点数等于边数 $+ 1$。
洛谷 P4652 - [CEOI2017] One-Way Streets
- 因为保证有解。我们考虑原图中边双里面的边无法确定方向，所以考虑缩边双。
- 缩完以后，现在相当于有一棵树的原问题。
- 可以树上差分，比如从 $x$ 到 $y$，让 $d[x]$ 加 $1$，$d[y]$ 减 $1$，这样边权为正代表向上，边权为负代表向下。
CF402E - Strictly Positive Matrix
- 矩阵乘法转化为计算路径的条数。
- 即询问是否存在 $k$ 使得所有 $i$ 到 $j$ 都有长度为 $k$ 的路径。
- 那么需要所有人都在一个强连通分量里面，注意存在某个点有自环，所以可以凑出长度为 $k$ 的路径。
洛谷 P3225 - [HNOI2012] 矿场搭建
- 将点双缩点变成一棵树，那么叶子节点一定要建，非叶子节点可以不用建。
- 单独讨论整个图是一个点双的情况。
二分图
- 二分图最大匹配：一定存在增广路，扩展所有增广路即可。
- 二分图最小点覆盖：左侧为匹配点开始 DFS，答案为左侧未 DFS 到的点 $+$ 右侧 DFS 到的点。
- 二分图最大独立集：最小点覆盖的补集。
洛谷 P1155 - [NOIP2008 提高组] 双栈排序
- 当只有一个栈的时候，怎样是合法的？
- 如果存在 $i < j < k$，$a_k < p_i < p_j$ 不合法。
- 对于两个栈的情况，我们找到所有不合法的 ，这两个人不能放在一起，想到二分图染色。
- 找到字典序最小的合法解。
洛谷 P2055 - [ZJOI2009] 假期的宿舍
洛谷 P4304 - [TJOI2013] 攻击装置
- 对棋盘黑白染色，有攻击关系建边。
- 那么就是二分图最大独立集 $= n -$ 最大匹配。
洛谷 P1129 - [ZJOI2007] 矩阵游戏
- 行和列都建点跑二分图匹配。
洛谷 P1263 - [CEOI2002] Royal guards
- 将连续的一段空地而不是一整行建成一个点，类似矩阵游戏的连边。
基环树
洛谷 P1453 - 城市环路
- 对于树来说，发现就是求最大独立集，设 $f[x][0 / 1]$ 表示 $x$ 点选或不选的最大值。
- 对于环来说，考虑断环为链，相邻两个点一定有一个是不选，分别枚举强制某个点不选做一次链上的 DP 即可。
洛谷 P4381 - [IOI2008] Island
- 考虑求一个基环树的直径，先求出树的直径。
- 对于环上的每个点，我们考虑记录 $f[x]$ 表示从 $x$ 开始到其子树内最长路径是多少。
- 断环为链，记录链上的路径前缀和，那么答案就是 $\max(f_i + f_j + s_j - s_i)$，$\max(f_i + f_j + len - (pre_j - pre_j))$，代表走环的两部分。
- 直接扫一遍即可。