浅谈图论中的割点、割边（桥）
浅谈图论中的割点、割边（桥）
作者：xiaoh
概念
首先，我们先要搞清楚的是，割点和桥一定是在无向图中的（有向图连强联通都保证不了谈个蛇的割点QAQ）。割点指的是在一张图中，如果删去一个点后，影响到了原图的连通性，例如原来图中是全部连通的，但删掉一个点以及所有与其相连的边后，这张图有了两个不同的连通块，那么就成这个点为这张图的割点啦。
在下图（图1）中，如果我们删去5号点，那么原来联通的图就变得不连通了，那么它就是割点QAQ
图一
当然，如果原本不连通的图，假设有2个连通块，而在删掉某个点后，它有了3个或以上的连通块，那么它也是割点。例如下图（图2）中的2号点和6号点
图二
注意：图中的1、5、7号点并不是割点，因为删掉这玩意丝毫没有改变图的连通性
算法-Tarjan
在讲算法前，应该先吐槽Tarjan这个人，他不但证明了并查集按秩合并的复杂度，发明了Splay，LCT,斐波那契堆，还提出了求LCA的离线算法，求强联通分量O（v+e）的算法，以及本文介绍的割点割边的算法QAQ （所以有时光机的话一定要穿越回去干掉他，这样就可以少做几道题了）
好了，言归正传，我们来讲一下这个算法的思路
首先，普及几个概念：
1、时间戳：按照DFS被访问到的先后顺序标号，每个点所标到的数字就是其时间戳。例如图2中点的标号就可以理解为其一种时间戳
2、搜索树：我们按照DFS的先后顺序将经过的点和DFS时经过的边把其建成一棵树，越早遍历到的点深度越小。下面给出一张图以及它的搜索树（为了使树更直观就用有向边来表示了QAQ，实际是无向图哦）：
这是原图：
图三
这是搜索树：
图四
当然，搜索树可以以任何一个节点为根，形态也可以有很多种，由于数量太多这里就只列了一种。
3、横叉边：指在原图中，但不在搜索树上的边，例如图三中从节点3到节点1的边就是横叉边。
4、双联通分量：原图的一张子图，且不存在割点。其实双联通分量也有很多应用，但由于篇幅原因就不赘述了。
接下来，为了方便讲解，我们定义一个数组low[n]，其中low[i]表示在搜索树中，i所在子树经过横叉边能到达的时间戳最小的点
还是拿图3和4作为栗子，我们根据搜索树给出节点1~5各自的DFN：{1，2，4，5，3，6}（当然也可以是{1，2，5，4，3，6}或者{1，2，6，5，3，4}，不过不影响程序的结果，后面讲到了就懂了）。节点3所在子树（其实就它一个）能到达时间戳最小的节点为节点1，时间戳为1，所以low[3]=1，由于节点3包含在节点5所在子树和节点2所在子树，而这两个子树能到达的DFN最小的点还是1，进而low[5],low[2]都等于1。同理，low[4]也等于1。而节点6所在子树哪里都去不了，所以low[6]=6。
好的，接下来我们就可以开始正题了，请自备纸笔，随时准备手动计算和模拟（干货警告……温馨提示：如果实在太毒瘤看不懂的话那么记住，只要看引理的内容，不看证明，相信证明你们自己想想也就懂了QAQ）：
引理0（废话定理）：一个点成为割点的充分且必要条件是，存在两个点，这两点之间的所有路径都必须经过这个割点
顾名思义，其实是废话，根据定义很容易推出来的。再不会人肉画图模拟就好了
引理0.5：搜索树上，一个点的两棵子树之间必定没有横叉边
证明很简单，若先访问的一棵子树（为方便简称早子树）中要是有一条边与后访问的一棵子树（为方便简称晚子树）相连，而搜索树又是DFS生成的，所以早子树若有与晚子树相连的横叉边，那么DFS时一定会在访问早子树时就会通过横叉边进入晚子树的某个部分，然后将这条横叉边与晚子树内部连接的那个点所在子树给接在了早子树内部。从而这条横叉边就是搜索树上的边了，而非横叉边。所以所有子树之间都无横叉边。大家再不懂的话可以拿图三或随便画张图自己试验一下，就会发现这个引理很明显是正确的。如果还读不懂的话也没关系，继续看下去吧，这并不是重点，只是笔者想证明一下算法的严谨性罢了。
怕你们不懂，举个栗子。我们看图三和图四。如果我们在图三中间节点3和节点6之间加一条边，那么原来的搜索树很明显就在两棵子树之间有了一条横叉边。那么图4依旧是图5的搜索树吗，如果不是，那么新的搜索树又是怎样的呢，我们来看看吧。
这是加了一条边后的图3：
图5
以下是新版的搜索树：
图6
很明显，原来连接节点3和节点6的横叉边变成了搜索树上的边，而将整个节点6所在的子树在访问节点3时就被访问过了，而不会将这条边单独以横叉边的形式出现。现在看看图3~6，依旧子树间没有任何一条横叉边。现在回头再看一遍引理0.5，或许你就懂了QAQ
引理1：除根外，一个点成为割点的充分且必要条件是，在搜索树上存在一条边（u,v）（其中u是v的父节点），使dfn[u]<=low[v]。
其实很好理解，我们可以先把整张图分成多个连通块，每一联通块内处理。我们先考虑单个连通块中，根据引理0我们可知，可以将这个子图内除了单个割点的点至少分成两组点，我们从这任意两组点中各取一个点，那么一定保证它们之间的所有路径都要经过割点，且每组点内任意两点之间总有一条路径不经过割点（其实就是将图分为多个双联通分量）。接下来考虑其搜索树，我们可以将整张图分成至少两部分，第一部分是搜索树上除割点所在子树以外的所有点，剩余部分为割点的所有子树。根据定义，上述的两组点必定不在同一部分中（否则它们之间的路径必定有一条不经过割点，那么这个点就一定不是割点了）。而同组的点一定在一棵子树中，否则这两个点之间的所有路径必定经过割点。（有人可能要问，我可以走横叉边啊，其实这是不行的，因为如果两棵子树之间不可能存在横叉边，定理0.5已经证明过了）接下来考虑反证法。假设存在割点u，其所有子树v1,v2,…,vk的low[vi]都小于dfn[u]，那么根据low的定义，那么每个点所在部分，无论是u的子树还是u父亲所在部分，都能通过横叉边相互到达，那么u就不是割点了QAQ
引理2：根节点成为割点的充分且必要条件为，它的儿子数量大于等于2
这个也很好理解，在DFS中，若根不是割点，那么每两个点之间肯定有至少2条路联通，那么这个双联通分量中的所有点一定会在一棵子树中被快乐地遍历到，而不会变成两棵子树。其实跟引理1有几分类似，也可以这么理解，因为根据引理0.5，根节点所有的子树一定互相没有横叉边。所以如果根有2个以上的子树，那么根一定是连接这两个子树的必经之路，也就是割点啦！（如果再不理解的话自己画两张图自己建建树就懂了）
因而得出结论，对于非根的每一个点，直接看它和儿子的low和dfn就好了，根的话直接数子树数量就好了。接下来我们的问题就聚焦在了怎样求每一个点的low值上了。鉴于前面的定义，我们知道:每个节点的low值就等于它所在子树能到达的最远的点。所以每个点的low值就是以下三个数的最小值：1、节点自身的DFN；2、节点所有儿子的low的最小值；3、节点自身通过横叉边能到达DFN最小的点。根据定义我们不难推出这三者最小值的正确性。由于之前的DFN是利用DFS的，不难想到我们可以在DFS遍历时将儿子的low值更新到自身的low值上，然后再遍历横叉边即可。
所以，割点算法也就很自然的出来了嘛：
首先，DFS递归地求出每个点的DFN，然后遍历经过这个点的横叉边（注意一定是横叉边，父节点需要特判），如果横叉边另一头的点的DFN小于自己的low，就更新，然后再看看自己的儿子，如果有low值小于自己的，就更新（根节点特判子树数量）就好了
接下来，就上个代码吧QAQ（c此处以洛谷P3388 割点作为模板）：
#include<bits/stdc++.h>
using namespace std;
inline int read()//快读不解释
{
register int ret=0;
register char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret;
}
inline void write(int x)//快些不解释
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
int n,m;//分别表示点数和边数
int tot=1;
int edge[1000010];//这里要注意，无向图边数要开2倍，我这里炸了半小时QAQ
int nxt[1000010];
int head[50010];
int sum=0;
bool ans[50010];
void add_edge(int u,int v)//前向星加边
{
edge[tot]=v;
nxt[tot]=head[u];
head[u]=tot++;
}
int low[20010];//low与前文所说的意思相同
int num[20010];//这个是每个节点的dfn
int dfn;//这个是动态给每个点分配dfn的计数器
void Tarjan(int p,int fa,int root)//算法DFS核心部分
{
low[p]=num[p]=++dfn;//先将时间戳和low都标记为dfn
bool flag=1;//flag表示这个点是否被记录为答案
int subtree=0;//如果是根节点还要数儿子
for(register int i=head[p];i;i=nxt[i])
{
int t=edge[i];
if(num[t]==0)//如果这个点还没被遍历，就递归DFS下去
{
subtree++;//快乐的找到了一个新儿子
Tarjan(t,p,root);
low[p]=min(low[p],low[t]);//更新low值
if(low[t]>=num[p]&&p!=root&&flag)//判断非根的割点
{
ans[p]=1;
flag=0;
sum++;
}
}
else if(num[t]<num[p]&&t!=fa) low[p]=min(low[p],num[t]);//如果是横叉边的话，也更新答案（注意特判父节点）
}
if(subtree>=2&&p==root) ans[p]=1,sum++;//根是否是割点
}
int main()
{
n=read(),m=read();//读入原图
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
if(u==v) continue;
add_edge(u,v);
add_edge(v,u);
}
for(int i=1;i<=n;i++)
if(num[i]==0) Tarjan(i,-1,i);//由于图未必是联通的，所以要多来几次
write(sum);//输出答案
putchar('\n');
for(int i=1;i<=n;i++)
if(ans[i]) write(i),putchar(' ');
}（码风有点丑，大佬勿喷）
接下来就是割边（也叫作桥）了。有了前面的铺垫，我们很容易就能猜到，桥就是说，我们在图中删掉一条边，会改变这张图的连通性。
我们回到最早的那张图一，就会发现，很明显，连接1和5的边就是桥了
图一×2