Tarjan 求割点
FLY_lai
·
·
个人记录
割点：删掉一个点后，整个图不再连通，称此点为割点。
我们想要求出一张图内所有割点，有一个很好的算法：Tarjan 算法。
【Tarjan 算法的预备】
Tarjan 算法主要依靠两个重要概念：
$low_i$，表示 $i$ 号结点通过 以 $i$ 为根的子树（以下子树均指搜索树中的子树）可以走到的 $dfn$ 最小的结点的 $dfn$ ，并且离开子树后就不许动了。
这两个概念比较难以理解，解释一番。
------------
这是一张无向图，其中黑色的边是深搜树里的边，蓝色的边是其余没用的边。
那么，我们可以写出每个点的 $dfn$ 。
图中的红色数字即 $dfn$，比较好理解。
我们再写出每个点的 $low$ 。
图中的黄色数字即 $low$ 。
下文 $n$ 号点 指 $dfn=n$ 的点
这里选几个典型：
1号点，它通过子树没法到达比它的 $dfn$ 更小的结点，因此它的 $low=1$。
这也很好理解，因为根结点不可能可以再往上走。
2号点，它的 $low=2$，因为它通过子树的边最多到达自己，即便是用了蓝色的非树边也只能到自己。
3号点，因为它可以先走到4号点，再通过一条蓝边到达2号点，因此 $low_3=2$。
**注意，3号点从蓝边走上去之后，就离开了3号点的子树，按照定义，不准动了，于是停在2号点。**
4号点，因为它可以直接通过蓝边走到2号点，因此 $low_4=2$。
**注意，与自己连的非树边也可以走。**
## 【Tarjan 算法】
那么，这两个东西有什么用？
主要是 $low$ 发挥了作用。
我们考虑一个割点。
如果删掉这个点，它一定把至少一棵子树 “切开” 了。
而可以把一棵子树 “切开” 的点，一定是割点。
### 什么叫把子树 “切开”？
我们发现，被切开的子树无法独立连接到 整张图 去掉 以割点为根的子树 剩下来的图 上面。
**又因为没有横向边**，一棵子树的 $low$ 所代表的结点，一定是它们的**直接祖先**；而且，一个点的直接祖先在深搜中一定更先访问到。
所以，如果一棵子树根的 $low$ 如果比这个点的 $dfn$ 小，删掉这个点之后，这一棵子树依然可以连着；
反之，如果一棵子树根的 $low$ 大于等于这个点的 $dfn$，删掉这个点之后，这一棵子树就被 “切开” 了。
### 如果一个点所有子树都不会被这个点 “切开”，这个点不是割点
### 如果一个点有子树会被这个点 “切开”，这个点是割点
------------
## 【实现的细节】
现在，如果有了 $dfn$ 和 $low$，我们就可以知道每个点是不是割点。
但是，我们要怎么求这两个东西呢？
$dfn$：全局变量记录当前已经搜了几个结点，**进入搜索的时候**更新。
$low$： 我们发现，$low$ 可以分两类。
1. 通过自己的非树边直接上去；
2. 通过子树的非树边间接上去。
这两者是不重不漏的，我们在两者之间取 **$min$** 即可。
第一类很好说，遍历自己所有的边，只要是非树边，就用对面的点更新一下。
第二类，还是遍历自己所有的边，只要通向子树，就先走下去搜，用返回的答案更新。
**如何转换成代码**
因为我们搜索的时候，有一个对点的 $vis$ 标记，如果一条边指向一个 $vis$ 标记为 $true$ 的点，说明这是一条往回走的边。
如果 $vis$ 标记为 $false$ 的点，说明这是一条通向子树的边。
**为什么会遍历到走向父结点的边但是不会出错？？？**
**因为本身不会用来更新本身，本身用来更新父结点。**
## 【Code】
```
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
int n, m;
vector<int> e[100005];
//dfn[i]为访问顺序，low[i]为i的子树结点能直接到达的最小dfn值
int dfn[100005] = {0}, low[100005], cur = 0, cntP = 0;//割点个数cntP
bool ans[100005] = {0};//ans[i]=true表示i为割点
int srh(int x, int rt) {//访问x并返回low[x],搜索树根为rt
low[x] = dfn[x] = ++cur;
for (int i = 0, cnt = 0; i < e[x].size(); i++)//cnt为子节点个数
if (dfn[e[x][i]] == 0) {//未访问过，去访问，形成树边
low[x] = min(low[x], srh(e[x][i], rt));
cnt++;
if (x != rt && low[e[x][i]] >= dfn[x])//非跟通过存在子树low值>=dfn[x]判断
ans[x] = true;
if (x == rt && cnt >= 2)//根通过多于一个子节点判断
ans[x] = true;
}
else //非树边，则用来更新自己的low值
low[x] = min(low[x], dfn[e[x][i]]);
cntP += ans[x];
return low[x];
}
int main()
{
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].push_back(v), e[v].push_back(u);
}
//找到一个dfn[i] == 0 则是一个新的连通分支，重新处理一遍
for (int i = 1; i <= n; i++)
if (dfn[i] == 0)
srh(i, i);
cout << cntP << endl;
for (int i = 1; i <= n; i++)
if (ans[i])
cout << i << " ";
cout << endl;
return 0;
}
```