当前位置：首页 > news >正文

tarjan进阶

news 来源：原创 2024/4/29 23:20:37

一、边双连通分量

定义

若一个无向图中的去掉任意一条边都不会改变此图的连通性，即不存在桥，则称作边双连通图。一个无向图中的每一个极大边双连通子图称作此无向图的边双连通分量。

实际求法和强连通分量差不多，只是要注意由于一条无向边被分为两条有向边存储，所以在经过其中一条从u到达v之后不能再通过另一条边由v返回u。

代码

inline void tarjan(int x,int fa){
      dfn[x]=low[x]=++cnt;
      a.push(x);
      ist[x]=1;
      int wh=0;
      for(int i=0;i<v[x].size();i++){
            if(v[x][i]==fa&&!wh){
              wh=1;
              continue;
            }
          if(!dfn[v[x][i]]){
            tarjan(v[x][i],x);
            low[x]=min(low[x],low[v[x][i]]);
          }else if(ist[v[x][i]]){
            low[x]=min(low[x],dfn[v[x][i]]);
          }
        }
      if(dfn[x]==low[x]){
          sum++;
          while(1){
            int u=a.top();
            a.pop();
            ist[u]=0;
            belong[u]=sum;
            if(u==x)break;
          }
      }
      return;
}

二、割点

定义

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

也就是说对于一条边的两个节点u和v，如果low[v]>=dfn[u]则u是一个割点（dfn[u]<dfn[v]）。

代码

inline void tarjan(long long x,long long fa){
      dfn[x]=low[x]=++cnt;
      long long son=0;
      for(long long i=0;i<v[x].size();i++)
        if(v[x][i]!=fa){
          if(!dfn[v[x][i]]){
            son++;
            tarjan(v[x][i],x);
            low[x]=min(low[x],low[v[x][i]]);
            if(low[v[x][i]]>=dfn[x])is[x]=1;
          }else low[x]=min(low[x],dfn[v[x][i]]);
        }
      if(!fa&&son==1)is[x]=0;
      return;
}

三、桥

定义

是存在于无向图中的这样的一条边，如果去掉这一条边，那么整张无向图会分为两部分，这样的一条边称为桥无向连通图中，如果删除某边后，图变成不连通，则称该边为桥。

实际求法和割点差不多，就是要将条件dfn[u]<=low[v]改成dfn[u]<low[v]

代码

inline void tarjan(int x,int fa){
      int wh=0;
      dfn[x]=low[x]=++cnt;
      for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=fa){
          if(!dfn[v[x][i]]){
              tarjan(v[x][i],x);
              low[x]=min(low[x],low[v[x][i]]);
              if(dfn[x]<low[v[x][i]])ans++;
          }else low[x]=min(low[x],dfn[v[x][i]]);
        }
      return;
}

以上是没有重边的情况，如果有则要这样写

代码

inline void tarjan(int x,int id){
      dfn[x]=low[x]=++T;
      for(int i=head2[x];i;i=nxt2[i])
        if((i+1)/2!=(id+1)/2){
          if(!dfn[to2[i]]){
              tarjan(to2[i],i);
              low[x]=min(low[x],low[to2[i]]);
              if(low[to2[i]]>dfn[x])is[id2[i]]=1,S++;;
          }else low[x]=min(low[x],dfn[to2[i]]);
        }
      return;
}

四、点双连通分量

定义

任意两个点之间存在至少两条点不重复路径。

实际上求点双是基于求割点的。我们每求到一个割点u便将之前栈里存储的点弹出，一直到v为止，注意要把u划到这个点双中但是不能将其弹出，因为一个割点可能属于多个点双。

代码（借用ttl的）

void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++tarcnt;
    st[++tp]=x;
    for(int k=g1[x];k;k=e1[k].next)
    {
        int y=e1[k].to;if (y==fa) continue;
        if (dfn[y]==0)
        {
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if (low[y]>=dfn[x]) 
            {
                int t;tot++;
                add(x,tot),add(tot,x);
                do {t=st[tp--],add(t,tot),add(tot,t);}while(t!=y);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}