tarjan 割点割边

by GeneralLiu

tarjan 求割点割边

无向图 的割点割边：

对于无向连通图来说，

　　如果删除一个点以及与它相连的边之后，

　　　　使得这个图不连通，

　　　　那么该点为割点；

　　如果删除一条边之后，

　　　　使得这个图不连通，

　　　　那么该边为割边；

tarjan 是基于 dfs树的算法

所以， dfs树上的一些术语有必要知道一下

so 看我博客

与有向图的tarjan算法非常类似

割边的求法（这个一步就判断出来，先写容易的）：

　　在 dfs树上后向边一定不是割边

　　　　如果是树边（from u,to v） // 对应下文代码 20 行

　　　　　　且 low [ v ] > dfn [ u ] // 对应下文代码 24,25 行

　　　　　　则是割边

在无向图这里边的类型只有这两种（没有横叉边与前向边）

割点的求法：

　　如果是 dfs树的根节点

　　　　且有不止一个儿子则是割点 // 对应下文代码 33,34 行

　　不是根

　　　　如果 u 存在子节点 v // 对应下文代码 28,29 行

　　　　　　使 low[v] >= dfn[u]

　　　　　　那么u为割点

代码

与有向图的tarjan代码非常类似

 #include<iostream>

 #include<cstdio>

 using namespace std;

 #define N 1000

 #define M 2000

 int dfn[N],low[N],cnt,n,m,head[N],to[M],next[M];

 bool cutnode[N],cutedge[M];

 void add(int x,int y){

     next[++cnt]=head[x];

     to[cnt]=y;

     head[x]=cnt;

 }

 void dfs(int fa,int u){

     dfn[u]=low[u]=++cnt;

     int v,ch=;

     bool b=;

     for(int i=head[u];i;i=next[i]){

         v=to[i];

         if(v==fa)continue;

         if(!dfn[v]){ // 树边

             ch++;

             dfs(u,v);

             low[u]=min(low[u],low[v]);

             if(low[v]>dfn[u])  // 判断 割边

                 cutedge[(i+)>>]=;  // 无向图边存了两遍 如此来定位 边的编号

         }

         else low[u]=min(low[u],dfn[v]);

         if(low[v]>=dfn[u]) // 判断 割点

             b=;

     }

     if(dfn[u]!=) // 讨论 u 是否 为根 分别处理

         cutnode[u]=b;

     else if(ch>=)

         cutnode[u]=;

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int x,y,i=;i<=m;i++){

         scanf("%d%d",&x,&y);

         add(x,y);

         add(y,x);

     }

     for(int i=;i<=n;i++)

         if(!dfn[i])

             cnt=,dfs(,i);

     for(int i=;i<=n;i++) // 输出 割点

         if(cutnode[i])

             printf("%d ",i);

     printf("\n");

     for(int i=;i<=m;i++) // 输出 割边

         if(cutedge[i])

             printf("%d ",i);

     return ;

 }

割边

tarjan 割点 割边

tarjan 割点割边