tarjan 算法学习笔记
GI录像机
·
·
算法·理论
前言
虽然学过了，但学得不是很清楚。故而洗点重来。
PS：请自行画图举例，这能帮助你更好地记住并掌握才不是因为懒得画图呢。
算法部分
tarjan 的两个核心数组
$low_i$：表示 $i$ 点不经过连向父亲的边能到达的 dfs 序最小的点的 dfs 序（暂时这样定义，这可以引申出后面的更好定义）。
## tarjan 求割边
我最开始学的是 tarjan 求强连通分量，但显然割边更适合入门。
### 定义
割边：对于一个无向图内的边，如果删去这条边后图的连通块数增加，那么这条边是割边。
### 做法
多个连通块的情况就是每个连通块的和，所以我们只考虑一个连通块的情况。
对一个无向图，先求出它的一个 dfs 树。容易发现，非树边都不会是割边，因为不需要它们所有的点也能形成一个树。
先不考虑怎么求 $low$，假设它是封装好的函数，可以直接调用。
考虑怎么用这两个数组判断一条树边是否是割边。设这条树边连接的两个点为 $u$ 和 $fa$（$fa$ 为 $u$ 的父亲）。当我们断开这条边后，树就会变成两个，我们只需要找到一条边连接 $u$ 的子树和其它点形成的连通块就能证明这条边不是割边。
图中 $u=6$，加粗的点和不加粗的点分别在两个不同的连通块内
如果存在一条非树边，连接 $u$ 的子树和其它点形成的连通块，那么 $low_u<dfn_u$。因为 $u$ 的祖先中一定有根节点，其 dfs 序为 $1$，这条边的存在会使 $low_u=1$。
否则 $low_u=dfn_u$，因为 $u$ 子树内 dfs 序最小的数是 $u$。
现在思考如何求出 $low$ 数组。发现这个定义不能简单地通过儿子转移，于是把它换成更好转移的定义。
设 $low_i$ 表示**至多经过一条非树边并且只经过 $i$ 子树内的树边所能到达的最小 dfs 序**。
这样的 $low$ 值实际上就是 $dfn_u$ 和子树连出的非树边连向点的 dfs 序的最小值。可以发现这样的 $low$ 仍然满足仅当 $low_u<dfn_u$ 时，边 $(u,fa)$ 不为割边。
这是由于 dfs 树的性质，非树边只会连接有直接祖先关系的点。这使得非树边要么连接的是子树内的点，要么连接的是 dfs 序更小的点。也就是说，从非树边跳两次是不必要的。如果连接的是子树内的点，那么完全可以从树边走过去；如果连接的是子树外的点，那么已经满足条件，无需再跳。
而这样的定义也让我们避免了从子树外通过树边走到 $(u,fa)$ 的情况。
实现看代码。
### 代码
[例题](https://www.luogu.com.cn/problem/AT_abc075_c)
```cpp
void tarjan(int pos, int fa) {
dfn[pos] = low[pos] = ++tot;
for(int i = head[pos]; i; i = e[i].nxt) {
if(!dfn[e[i].to]) {//树边
tarjan(e[i].to, pos);
low[pos] = min(low[pos], low[e[i].to]);
if(low[e[i].to] == dfn[e[i].to])ans++;
} else if(e[i].to != fa)low[pos] = min(low[pos], dfn[e[i].to]);//树外边
}
}
```
## tarjan 求割点
### 定义
割边：对于一个无向图内的点，如果删去这个点后图的连通块数增加，那么这个点是割点。
### 做法
与求割边类似，对于非根节点 $u$，如果存在一个儿子 $v$ 使得 $low_v=dfn_v$ 或 $low_v=dfn_u$，那么点 $u$ 是割点。
$low$ 的优秀定义再次帮助了我们。由于非树边只会走一条，所以我们可以轻松看出当前的 $low$ 是否经过了点 $u$。
对于根节点，由于无向图的 dfs 树的非树边只会连接祖先后代，而根节点没有祖先，所以只需要看根节点的子树数量是否大于 $1$ 即可。
你也可以通过把边当作点，点当作边的方式求解。
### 代码
[例题](https://www.luogu.com.cn/problem/P3388)
```cpp
void tarjan(int pos, int root) {
dfn[pos] = low[pos] = ++cnt;
for (int i = head[pos]; i; i = e[i].nxt) {
if (!dfn[e[i].to]) {
if (root == pos)rt++;
tarjan(e[i].to, root);
if ((low[e[i].to] == dfn[pos] || low[e[i].to] == dfn[e[i].to]) && root != pos)cut[pos] = 1;
low[pos] = min(low[pos], low[e[i].to]);
} else low[pos] = min(low[pos], dfn[e[i].to]);
}
if (rt >= 2 && root == pos)cut[pos] = 1;
}
```
## tarjan 求边双连通分量
### 定义
边双连通分量：对于一个无向图，不存在桥的极大连通子图即为一个边双连通分量。
### 做法
将所有遍历到的点压入一个栈内，遍历是按 dfs 序的，所以入栈也是按 dfs 序的。当遇到 $dfn_u=low_u$ 时，代表边 $(u,fa)$ 是一条割边，不能出现在边双里面。
不断出栈直到弹出点 $u$，这些同一次出栈的点在一个边双里面。这是因为在 $u$ 后入栈的点都在其子树内，而子树内的割边所连的点都已经全部出栈。
### 代码
[例题](https://www.luogu.com.cn/problem/P8436)
```cpp
void tarjan(int pos, int las) {
dfn[pos] = low[pos] = ++cnt;
st.push(pos);
for(int i = head[pos]; i; i = e[i].nxt) {
if(!dfn[e[i].to]) {
tarjan(e[i].to, i);
low[pos] = min(low[pos], low[e[i].to]);
} else if(i != (las ^ 1))low[pos] = min(low[pos], dfn[e[i].to]);
//本题可能有重边，las 和 las ^ 1 分别表示一条无向边的两个方向
}
if(dfn[pos] == low[pos]) {
ans[++scc].push_back(pos);
while (pos != st.top()) {
ans[scc].push_back(st.top());
st.pop();
}
st.pop();
}
}
```
## tarjan 求点双连通分量
### 定义
点双连通分量：对于一个无向图，不存在割点的极大连通子图即为一个点双连通分量。
### 做法
与边双连通分量不同的是，整个图的割点可以出现在点双连通分量中多次。
上图中，红边为树外边，绿色部分和蓝色部分分别为两个点双连通分量。
原因是原图的割边加入边双中就会使连接的两个点加入边双，从而导致割边在边双中也是割边；而原图的割点加入点双中并不会使和它连接的所有点加入点双。
对于一个点 $u$，当遇到儿子 $v$ 满足 $low_v=dfn_v$ 或 $low_v=dfn_u$ 时，子树 $v$ 会使 $u$ 变成割点。因此不断出栈直至弹出 $v$，这些点和 $u$ 构成一个点双。
对于根节点，无需特殊判断，直接当作割点即可。这是因为当根节点不为割点时，我们也需要把剩下的点塞进一个点双里面。
### 代码
[例题](https://www.luogu.com.cn/problem/P8435)
```cpp
void tarjan(int pos, int las) {
//本题还需要判断自环
dfn[pos] = low[pos] = ++cnt;
st.push(pos);
for(int i = head[pos]; i; i = e[i].nxt) {
if(!dfn[e[i].to]) {
tarjan(e[i].to, i);
low[pos] = min(low[pos], low[e[i].to]);
if(low[e[i].to] == dfn[e[i].to] || low[e[i].to] == dfn[pos]) {//对于子树 e[i].to，pos 是割点或根
ans[++scc].push_back(pos);
ans[scc].push_back(e[i].to);
while(e[i].to != st.top()) {//弹出 e[i].to 的子树
ans[scc].push_back(st.top());
st.pop();
}
st.pop();
}
} else if(i != (las ^ 1))low[pos] = min(low[pos], dfn[e[i].to]);
}
if(!las && !head[pos])ans[++scc].push_back(pos);//独立点
}
```
## tarjan 求强连通分量
### 定义
强连通分量：对于一个有向图，任意两点能够互相到达的极大连通子图为强连通分量。
### 做法
重新定义 $low_i$，表示和 $i$ 强连通的，dfs 序最小的点的 dfs 序。
延续前面的做法，考虑在一个强连通分量内，选出一个点 $u$ 作为代表，满足 $low_u=dfn_u$。
对于所有在 $u$ 子树内部连的边，走向的 dfs 序最小的点唯一，就是 $u$。对于 $u$ 子树内向外部连的边，如果连接的是 $u$ 的祖先，那么这些点就和祖先强连通，与前提矛盾。所以强连通分量内不会出现向 $u$ 的祖先连的边。
但是有向图的 dfs 树还有可能向以前访问过的其它点连边。假设该边为 $(u,v)$。如果 $v$ 没有一种路径可以到达它和 $u$ 的共同祖先，也就是不强连通。这就导致了 $low_u<dfn_u$，在强连通分量内找不到代表。
这是容易解决的。如果 $v$ 不和 $u、v$ 的最近公共祖先强连通，那么在处理 $u$ 之前，$v$ 所属的强连通分量就应该统计过了。只需要记录哪些点被统计过，不用这些点转移 $low$ 即可。
由于强连通具有传递性，所以不存在一个点同时在两个强连通分量内的情况。
事实上，在下面的示例代码中，$low$ 的含义和我们这里定义的并不一样，它是至多经过一条非树边并且只经过 $i$ 子树内的树边所能互相到达的最小 dfs 序。
按照我们的定义，`else if (vis[e[i].to])low[pos] = min(low[pos], dfn[e[i].to]);` 应为 `else if (vis[e[i].to])low[pos] = min(low[pos], low[e[i].to]);`。
但两者都是正确的，原因留给读者自己思考。
### 代码
[例题](https://www.luogu.com.cn/problem/B3609)
```cpp
void tarjan(int pos) {
dfn[pos] = low[pos] = ++cnt;
vis[pos] = 1;
st.push(pos);
for (int i = head[pos]; i; i = e[i].nxt) {
if (!dfn[e[i].to]) {
tarjan(e[i].to);
low[pos] = min(low[pos], low[e[i].to]);
} else if (vis[e[i].to])low[pos] = min(low[pos], dfn[e[i].to]);
}
if (dfn[pos] == low[pos]) {
ans[++scc].push_back(pos);
belong[pos] = scc;
vis[pos] = 0;
while (st.top() != pos) {
ans[scc].push_back(st.top());
belong[st.top()] = scc;
vis[st.top()] = 0;
st.pop();
}
st.pop();
}
}
```
## 缩点
说了这么多，这几个连通分量到底有什么用呢？
如果题目的性质能让我们把图中的边双连通分量/点双连通分量/强连通分量视作一个点，那么这个图会有非常好的性质。
下面我们用强连通分量举例：
如下图，每种颜色所圈的都是一个强连通分量。
缩点后：
发现缩点之后形成了一个 DAG（有向无环图）。因为若有环，则环上的强连通分量是强连通的，不符合前提。
同理，边双连通分量缩点后会形成一棵树。
### 代码
[例题](https://www.luogu.com.cn/problem/P3387)
强连通分量缩点后直接在 DAG 上处理即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int M = 100010, N = 10010;
int n, m, head[N], tot, cnt, low[N], dfn[N], scc, belong[N], sum[N], val[N], in[N], dp[N], ans;
stack<int>st;
bool vis[N];
struct Node {
int to, nxt;
} a[M];
struct node {
int u, v;
} b[M];
void add(int u, int v) {
a[++tot].to = v;
a[tot].nxt = head[u];
head[u] = tot;
}
void tarjan(int pos) {
dfn[pos] = low[pos] = ++cnt;
vis[pos] = 1;
st.push(pos);
for (int i = head[pos]; i; i = a[i].nxt) {
if (!dfn[a[i].to]) {
tarjan(a[i].to);
low[pos] = min(low[pos], low[a[i].to]);
} else if (vis[a[i].to])low[pos] = min(low[pos], dfn[a[i].to]);
}
if (dfn[pos] == low[pos]) {
scc++;
int now = 0;
while (now != pos) {
now = st.top();
belong[now] = scc;
sum[scc] += val[now];
st.pop();
}
}
}
void init() {
memset(head, 0, sizeof(head));
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
cnt = scc = tot = 0;
}
int main() {
n = read();
m = read();
for (int i = 1; i <= n; i++)val[i] = read();
for (int i = 1; i <= m; i++) {
b[i].u = read();
b[i].v = read();
add(b[i].u, b[i].v);
}
for (int i = 1; i <= n; i++)if (!dfn[i])tarjan(i);
init();
for (int i = 1; i <= m; i++) {
if (belong[b[i].u] == belong[b[i].v])continue;
add(belong[b[i].u], belong[b[i].v]);
++in[belong[b[i].v]];
}
queue<int>q;
for (int i = 1; i <= n; i++)
if (!in[i]) {
q.push(i);
dp[i] = sum[i];
}
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = head[now]; i; i = a[i].nxt) {
int v = a[i].to;
in[v]--;
dp[v] = max(dp[now] + sum[v], dp[v]);
if (!in[v])q.push(v);
}
}
for (int i = 1; i <= n; i++)ans = max(dp[i], ans);
write(ans);
return 0;
}
```
## tarjan 求 2-SAT
### [定义](https://www.luogu.com.cn/problem/P4782)
### 做法
满足 $x_i \vee x_j$ 等价于满足：若 $\neg x_i$，则 $x_j$；若 $\neg x_j$ 则 $x_i$。
对每个变量 $x_i$，我们在图上建两个点 $x_i$ 和 $\neg x_i$。将若 $\neg x_i$，则 $x_j$ 的条件转化为连接 $\neg x_i$ 和 $x_j$ 的有向边。这样我们的图就具有了推导的意义——如果在图上能从 $a$ 到 $b$，那么必然能从 $a$ 推出 $b$。
考虑什么情况下无解。显然如果 $\neg x$ 和 $x$ 能够互相到达那么是无解的。可以用 tarjan 求强连通分量来判断。
如果有解又该怎么找到一组解呢？如果 $\neg x$ 能够到达 $x$，那么必然选择 $x$ 为真，否则矛盾。反之亦然。可以通过缩点后的拓扑序来判断。
实际上，通过 tarjan 算法求出的强连通分量编号即为其缩点后的反拓扑序。想一想，为什么？
### 代码：
```cpp
signed main() {
for(int i = 1; i <= m; i++) {
int u = read(), a = read(), v = read(), b = read();
if(a && b)add(u + n, v), add(v + n, u);
else if(a)add(u + n, v + n), add(v, u);
else if(b)add(v + n, u + n), add(u, v);
else add(u, v + n), add(v, u + n);
}
for(int i = 1; i <= 2 * n; i++)if(!dfn[i])tarjan(i);
bool flag = 0;
for(int i = 1; i <= n; i++) {
if(belong[i] == belong[i + n])flag = 1;
ans[i] = (belong[i] < belong[i + n]);
}
if(flag)puts("IMPOSSIBLE");
else {
puts("POSSIBLE");
for(int i = 1; i <= n; i++) {
putchar('0' + ans[i]);
putchar(' ');
}
}
return 0;
}
```
# 例题：
[P3469 [POI2008] BLO-Blockade](https://www.luogu.com.cn/problem/P3469)
[P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G](https://www.luogu.com.cn/problem/P2341)
[ P2272 [ZJOI2007] 最大半连通子图 ](https://www.luogu.com.cn/problem/P2272)
## 绘图工具
[Graph Editor](https://csacademy.com/app/graph_editor/)
[智绘教](https://github.com/Alan-CRL/Intelligent-Drawing-Teaching)