Tarjan求割点与桥

2024-02-04 14:38

文章标签 tarjan 求割点

本文主要是介绍Tarjan求割点与桥，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

割点与桥的概念

割点：

简单的说就是，删掉这个点和这个点有关的边，图就不是连通图，分裂成了多个不连接的子图。

桥：

删掉这条边后，图就不再是连通图，分裂成为多个不连通的子图。

求割点

算法思想：

首先选定一个根节点，从根节点开始遍历整个图(使用dfs)

对于根节点：
如果有2棵即以上的子树，就是割点（因为如果去掉这个点，这两棵子树就不能互相到达）
对于非根节点
如果节点U的所有孩子节点可以不通过父节点U而访问到U的祖先节点，那么说明：即使去掉节点U也不影响图的连通性，U不是割点。
如果节点U至少存在一个孩子节点，必须通过父节点U才能访问到U的祖先节点，那么去掉节点U之后，顶点U的祖先节点和孩子节点就不连通了，此时U是一个割点。

维护数组

对于求割点的Tarjan算法数组中，其意义大体类似于求连通分量，但是略有不同

dfn[ ]：依然表示顶点u被首次搜到的序号
low[u]：表示顶点u及其子树中的点，通过非父子边（回边），能够绕到的最早的点(dfn最小)的dfn值(但不能通过连接u与其父节点的边)。这里不再是最早的祖先了，因为是无向图，所以并没有意义。
cut[u]:表示u是否为割点

low[u]的计算

若当前顶点为u，则low[u]=dfn[u]，即最早只能回溯到自身。
对于边(u,v)：
如果v未访问过，继续DFS，DFS完之后，low[u] =min(low[u],low[v]);
如果v访问过（且u不是v的父亲），就不需要继续DFS了，因为一定有dfn[v]<dfn[u] , low[u] = min(low[u],dfn[v])。

关于为什么是low[u]=min(low[u],dfn[v])而不能是low[u]=min(low[u],low[v])
(ps：这个是本人在学习时最为不解的地方)

在求强连通分量时，其实即使换掉也没有问题，这是因为如果v已经在栈中，那么说明u，v一定在同一个强连通分量中，所以到最后low[u]=low[v]是必然的，提前更新也不会有什么问题
但是在求割点时，由于是无向图，所以我们在存图的时候一个边存了两便，而我们必须要绕开连接u及其父节点的边，此时如果v恰好是u的父节点（u,v之间有边相连）且只有这么一条路径，那么我们更换后无法绕开那条边，所以就会出现问题。

在这里插入图片描述
上面数组的标号即为dfs序，当你用两种方法去模拟时，并观察2是否为割点时，你就能比较清楚的感觉到这里为什么要这样。

代码模板

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+20;
int head[N],edge[N<<1],Next[N<<1],tot;
int dfn[N],low[N],n,m,num,root,ans;
bool cut[N];
void add_edge(int a,int b)
{edge[++tot]=b;Next[tot]=head[a];head[a]=tot;
}
void Tarjan(int x)
{dfn[x]=low[x]=++num;int flag=0;for(int i=head[x];i;i=Next[i]){int y=edge[i];if(!dfn[y]){Tarjan(y);low[x]=min(low[x],low[y]);if(low[y]>=dfn[x]){flag++;if(x!=root||flag>1)cut[x]=true;}}else low[x]=min(low[x],dfn[y]);}
}
int main()
{scanf("%d%d",&n,&m);memset(cut,false,sizeof(cut));for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);add_edge(a,b);add_edge(b,a);}for(int i=1;i<=n;i++)if(!dfn[i]) {root=i;Tarjan(i);}for(int i=1;i<=n;i++)if(cut[i]) ans++;printf("%d\n",ans);for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i);//system("pause");return 0;
}

求桥

桥的求法其实类似的，它的求法可以看成是割点的一种特殊情况，当结点u的子结点v的后代通过反向边只能连回v，那么删除这条边(u,v)就可以使得图G非联通了。用Tarjan算法里面的时间戳表示这个条件，就是low[v]>dfn[u]

代码模板

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int head[N],edge[N<<1],Next[N<<1],tot;
int dfn[N],low[N],n,m,num;
bool bridge[N<<1];
void add_edge(int a,int b)
{edge[++tot]=b;Next[tot]=head[a];head[a]=tot;
}
void Tarjan(int x,int Edge)
{dfn[x]=low[x]=++num;for(int i=head[x];i;i=Next[i]){int y=edge[i];if(!dfn[y]){Tarjan(y,i);low[x]=min(low[x],low[y]);if(low[y]>dfn[x])bridge[i]=bridge[i^1]=true;}else if(i!=(Edge^1))low[x]=min(low[x],dfn[y]);}
}
int main()
{scanf("%d%d",&n,&m);tot=1;for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);add_edge(a,b);add_edge(b,a);}for(int i=1;i<=n;i++)if(!dfn[i]) Tarjan(i,0);for(int i=2;i<=tot;i=i+2)if(bridge[i])printf("%d %d\n",edge[i^1],edge[i]);//system("pause");return 0;
}