tarjan 求割点

时间:2022-04-16 18:53:49

在无向连通图中,如果将其中一个点以及所连的所有边都删掉,图就不再连通的话,那么这个点就叫做割点

首先将所有的点分为:1.环中点 2.不成环的单点
割点一般出现的情况是:如果(处在不同环中/一环一单点/均为单点)的两点相连,那么这两点都是割点

与tarjan求强连通分量相同,引入dfn时间戳和low
dfn意义还是记录遍历序号
low意义为记录自己当前点所在环的最先遍历的点的dfn,那么对于两个不同的环(或不成环的点)而言,他们low值一定不同

tarjan 求割点

下面分析判断割点:
如图,走dfs序,root黑色根节点最先进入,走了一圈又回到黑色节点,那么回溯过程做两件事:a.与黑色节点相邻的X, Low[X]=Dfn(黑)=low0, b.红色节点Low(红)=Low[X]=low0,然后红色节点分三路,三路回溯完后:
1.研究红蓝节点有low0<low1,那么回溯到红色节点时,一定会出现Dfn(红)<Dfn(蓝)=Low(蓝),此时标记红节点。
2.而红节点本身的环内节点回溯只会是Dfn(红)>Dfn(X)=low0。
3.那么蓝点其实也是割点,他什么时候被标记呢?回答:走自己蓝环时就要被标记,也就是说蓝环内部回溯到蓝点时,会出现Dfn(蓝)=Low(Y)=low1,这时标记蓝点。

总结下:
对于一个根节点:
如果有两颗以上的子树那么就是割点,(且注意红环回溯到黑点时,黑点不能通过Dfn(黑)=Low(红)=low0打标记)
对于非根节点:
综合上面123条,如果回溯满足 Dfn(u)<=Low(v),那么就把u打上标记即可。

上代码:(对于多个连通图的一般情况代码)

bool cut[N]//标记割点
int child=;//记录主根root有几个子树
void tarjan(int u,int fa){ //有fa是对于多连通图问题
dfn[u]=low[u]=idx++;
int child=;
for(i,fi[u],nx){
int v=e[i].to;
if(!dfn[v]){
tarjan(v,fa);
chkmin(low[u],low[v]);
if(low[v]>=dfn[u]&&u!=fa)cut[u]=;//打标记
if(u==fa)child++;
}
chkmin(low[u],dfn[v]);//管你以前遍历过没,如果遇到遍历过的点,那就相当于形成环了,那么更新dfn,而不是更新low,小心环套环情况
}
if(child>=&&u==fa)cut[u]=;
} For(i,,n)
if(!dfn[i])tarjan(i,i);
For(i,,n)
if(cut[i])ans++;