割和桥
割
又是tarjan.....
先来看看模板的题面。
给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。
什么是割点？
对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点。
比如现在有这么一张图
把点 $1,7,2,5$ 中其中一个删掉，这个图就变成了两部分，所以这四个点就是这张图的割。
怎么求？
暴力
枚举每个点，删除每个点之后再遍历一遍，不连通就代表刚才删除了一个割。
时间复杂度 $\Theta(n^2+nm)$，显然不可接受。
可以使用Tarjan算法求割点。
void tarjan(int u,int fat)
{
low[u]=dfn[u]=++cur;
int ch=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(!dfn[v])
{
tarjan(v,fat);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u] && u!=fat)
{
ans[u]=1;
}
if(u==fat)
{
ch++;
}
}
low[u]=min(low[u],dfn[v]);
}
if(ch>=2)
{
if(u==fat)
{
ans[u]=1;
}
}
}
假设我们从点1开始搜索，把搜过的点染一个色,其中红色代表的是 $\text{dfn[i]}$(时间戳)。
这个时候点 $1$ 可以向 $3,5,7$ 搜索。
浅绿色代表 $\text{low[i]}$(可记录每个顶点在不经过父顶点时，能够回到的最小dfn)，深绿色代表一次回溯的过程。
首先这里摆出一个定理：对于一个点 $u$，如果至少有一个点 $v$ 与 $u$ 连通，使得 $\text{low[v]}\le \text{dfn[u]}$成立，那么u点为割点。
对于上图中的点 $1$，显然存在一个点 $3$，对于$ \text{low[3]}\le \text{dfn[1]}$ 成立，所以 $1$ 是一个割点。
接下来的过程便是再次对于图上的点进行tarjan算法即可(这张图是对称的！)。
时间复杂度:大约是 $\Theta(nm)$。
正确性
$\text{low[v]}\le \text{dfn[u]}$成立，那么就代表从 $v$ 不能再向上回溯($\text{low[i]}$记录的是最小时间戳)，只能回溯到 $u$ 这就代表 $u$ 是一个割点。
桥
也就是割边。