无向图的割边、割点-白红宇

无向图的割边、割点

阅读量：5753 次

发布时间：2019-06-18

本文共 1909 字，大约阅读时间需要 6 分钟。

我们今天要来说一个新的东西：割边，割点。

显然，又有人要问了：什么是无向图的割边，割点？？？

好，我们先来解决这个问题。

一、定义

割边：对于无向连通图来说，如果删除一条边之后使得这个图不连通，那么该边为割边

割点：对于无向连通图来说，如果删除一个点以及与它相连的边之后，那么该点为割点

二、割边割点的求法

1.割点的求法

对于一个点u，

1.u为dfs搜索树的根，如果搜索树中它有大于一个的子节点，那么为割点；

2.u不为dfs搜索树的根，如果u存在子节点v使low[v]>=dfn[u],那么u为割点

2.割边的求法

对于一条边(u,v),

1.如果(u,v)是后向边，一定不是割边；

2.如果(u,v)是树边，那么如果low[v]>dfn[u],那么是割边；边的类型只有这两种（没有横叉边与前向边）

　　　　什么是树边，前向边，后向边，横叉边

三。板子

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 1000000using namespace std;bool vis[N];int n,m,x,y,tot,tim;int dfn[N],low[N],head[N],cut_edge[N],cut_point[N];struct Edge{    int next,to,from;}edge[N];void add(int x,int y){    edge[tot].to=y;    edge[tot].next=head[x];    head[x]=tot;    tot++;//在这里我们从0号开始对边进行编号，这样可以让同两个点件的两条边更有联系。0/2=0；1/2=0；2/2=1；3/2=1.。。。。 }int tarjan(int now,int pre)//pre为now点的父边 {    int sum=0; bool boo=0;    vis[now]=true;    dfn[now]=low[now]=++tim;    for(int i=head[now];i!=-1;i=edge[i].next)    {        int t=edge[i].to;        if((i^1)!=pre)//i为树边，存在low[v]>=dfn[u]则为割边。          if(!vis[t])         {             sum++;             tarjan(t,i);             if(low[t]>dfn[now]) cut_edge[i/2]=1;             if(low[t]>=dfn[now]) boo=false;             low[now]=min(low[now],low[t]);         }        else low[now]=min(low[now],dfn[t]);    }    if(pre==-1)//也就是说这个点是根节点，这样就满足：如果u为搜索树的跟，存在大于1的节点，则这个点为割点。       {if(sum>1) cut_point[now]=1;}else if(boo==1) cut_point[now]=1;//如果u不是搜索树的根，存在一个节点v使low[v]>=dfn[u]则这个点为割点。     return 0; }int main(){    scanf("%d%d",&n,&m);    memset(head,-1,sizeof(head));    for(int i=1;i<=m;i++)     scanf("%d%d",&x,&y),add(x,y),add(y,x);//建立双向边：无向图     for(int i=1;i<=n;i++)      if(!vis[i]) tarjan(i,-1);    for(int i=1;i<=n;i++)     if(cut_point[i]) printf("%d ",i);    return 0;}