tarjan

tarjan

还记得寒假集训没好好学 $tarjan$ ，一直就不咋会，所以趁着考前重新学了一下。

$tarjan$ 的基本运用主要有：

$1.$ 有向图中将若干点缩成一个点，建出一个 $DAG$ ,搭配各类最短路写法或拓扑排序使用

$code$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int n,m;
int a[N];
struct Graph{
    int head[N],tot,cnt,ntime,top,stk[N],low[N],dfn[N],bl[N],d[N],vis[N];
    long long sum[N];
    struct Node{int from,to,nest;}bian[N*10];
    void add(int x,int y){bian[++tot]=(Node){x,y,head[x]};head[x]=tot;d[y]++;}
    void tarjan(int x){
        dfn[x]=low[x]=++ntime;
        vis[x]=1,stk[++top]=x;
        for(int i=head[x];i;i=bian[i].nest){
            int v=bian[i].to;
            if(!dfn[v]){
                tarjan(v);
                low[x]=min(low[x],low[v]);
            }
            else if(vis[v])low[x]=min(low[x],dfn[v]);
        }
        if(dfn[x]==low[x]){
            cnt++;
            do{
                vis[stk[top]]=0;
                bl[stk[top]]=cnt;
                sum[cnt]+=a[stk[top]];
            }while(x!=stk[top--]);
        }
    }
}G1,G2;
void build(){
    for(int i=1;i<=n;i++)if(!G1.dfn[i])G1.tarjan(i);
    for(int i=1;i<=m;i++)if(G1.bl[G1.bian[i].from]!=G1.bl[G1.bian[i].to])G2.add(G1.bl[G1.bian[i].from],G1.bl[G1.bian[i].to]);
}
int q[N],l,r;
long long dis[N],ans;
void topsort(){
    l=1,r=0;
    for(int i=1;i<=G1.cnt;i++){
        if(G2.d[i]==0)q[++r]=i,dis[i]=G1.sum[i],ans=max(ans,dis[i]);
    }
    while(l<=r){
        int cc=q[l++];
        for(int i=G2.head[cc];i;i=G2.bian[i].nest){
            int v=G2.bian[i].to;
            dis[v]=max(dis[v],dis[cc]+G1.sum[v]);
            ans=max(ans,dis[v]);
            G2.d[v]--;
            if(G2.d[v]==0)q[++r]=v;
        }
    }
    printf("%lld\n",ans);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        int s1=0,s2=0;
        scanf("%d%d",&s1,&s2);
        G1.add(s1,s2);
    }
    build();
    topsort();
    return 0;
}

$2.$ 无向图中求割点或割边（桥）。

$3.$ 点双联通分量与边双联通分量

对于这两部分，我一直记不住，但理解一下就记得很深了。

对于割点的求法，有一句最关键的 $low_v \ge dfn_u$,意味 $v$ 不可能通过其他横叉边或返祖边到达 $u$ 的祖先，意味 $v$ 想到达 $u$ 的祖先一定要经过 $u$，则 $u$ 就是一个割点；对于一开始出发的点，他想要成为一个割点，那么他必然至少有 $2$ 条边。

对于割边的求法，有一句最关键的是 $low_v > dfn_u$,意味 $v$ 不可能通过其他横叉边或返祖边到达 $u$ 的祖先，意味 $v$ 想到达 $u$ 的祖先一定要经过边 $(u,v)$，所以边 $(u,v)$ 为桥。

对于点双与边双，实质上就是求割点与割边的过程，我们可以通过一遍 $tarjan$ 求出所有的割点或割边，再经过一遍 $dfs$ ,不经过割点或割边求出相应的双联通分量。

对于点双，我们也可以通过一遍 $tarjan$ 求出，具体与建圆方树的方法一致，下面的代码写的是这种做法。

对于边双，我们因为无法处理单点为双联通分量的情况，我们可以新建一个超级点，再跑 $tarjan$，也可以用一次 $tarjan$ 求出边双

$code$

割点

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e4+10;
int n,m;
struct Graph{
    int head[N],low[N],dfn[N],ntime,tot,cnt,cut[N];
    struct Node{int to,nest;}bian[N<<4];
    void add(int x,int y){bian[++tot]=(Node){y,head[x]};head[x]=tot;}
    void tarjan(int x,int fa){
        dfn[x]=low[x]=++ntime;
        int kid=0;
        for(int i=head[x];i;i=bian[i].nest){
            int v=bian[i].to;
            if(!dfn[v]){
                kid++;
                tarjan(v,x);
                low[x]=min(low[x],low[v]);
                if(low[v]>=dfn[x])if(x!=fa&&!cut[x])cut[x]=1,cnt++;
            }
            else if(v!=fa)low[x]=min(low[x],dfn[v]);
        }
        if(x==fa&&kid>=2&&!cut[x])cut[x]=1,cnt++;
    }
}G;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int s1=0,s2=0;
        scanf("%d%d",&s1,&s2);
        G.add(s1,s2),G.add(s2,s1);
    }
    for(int i=1;i<=n;i++)if(!G.dfn[i])G.tarjan(i,i);
    printf("%d\n",G.cnt);
    for(int i=1;i<=n;i++)if(G.cut[i])printf("%d ",i);
    return 0;
} 

割边（因为下面边双有写，我就不再写了）

点双

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=5e5+10;
int n,m;
struct Graph{
    int head[N],tot,ntime,cnt,dfn[N],low[N],stk[N],top;
    vector<int>vDCC[N];
    struct Node{int to,nest;}bian[N<<3];
    void add(int x,int y){bian[++tot]=(Node){y,head[x]};head[x]=tot;}
    void tarjan(int x,int fa){
        int son=0;
        dfn[x]=low[x]=++ntime;
        stk[++top]=x;
        for(int i=head[x];i;i=bian[i].nest){
            int v=bian[i].to;
            if(!dfn[v]){
                son++;
                tarjan(v,x);
                low[x]=min(low[x],low[v]);
                if(low[v]>=dfn[x]){
                    cnt++;
                    do{vDCC[cnt].push_back(stk[top]);}while(v!=stk[top--]);
                    vDCC[cnt].push_back(x);
                }
            }
            else if(v!=fa)low[x]=min(low[x],dfn[v]);
        }
        if(!son&&!fa)++cnt,vDCC[cnt].push_back(x);
    }
}G;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int s1=0,s2=0;
        scanf("%d%d",&s1,&s2);
        G.add(s1,s2),G.add(s2,s1);
    }
    for(int i=1;i<=n;i++)if(!G.dfn[i])G.tarjan(i,0);
    printf("%d\n",G.cnt);
    for(int i=1;i<=G.cnt;i++,putchar('\n')){
        printf("%u ",G.vDCC[i].size());
        for(auto v : G.vDCC[i])printf("%d ",v);
    }
    return 0;
}

边双

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=5e5+10;
int n,m;
struct Graph{
    int head[N],cnt,tot,ntime,dfn[N],low[N],vis[N],is_bridge[N<<3];
    vector<int>eDCC[N];
    Graph(){tot=1;}
    struct Node{int to,nest;}bian[N<<3];
    void add(int x,int y){bian[++tot]=(Node){y,head[x]};head[x]=tot;}
    void tarjan(int x,int fa){
        dfn[x]=low[x]=++ntime;
        for(int i=head[x];i;i=bian[i].nest){
            int v=bian[i].to;
            if(!dfn[v]){
                tarjan(v,x);
                low[x]=min(low[x],low[v]);
                if(low[v]>dfn[x]){
                    is_bridge[i]=1;
                    is_bridge[i^1]=1;
                }
            }
            else if(v!=fa)low[x]=min(low[x],dfn[v]);
        }
    }
    void dfs(int x){
        vis[x]=1;
        eDCC[cnt].push_back(x);
        for(int i=head[x];i;i=bian[i].nest){
            if(is_bridge[i])continue;
            int v=bian[i].to;
            if(vis[v])continue;
            dfs(v);
        }
    }
    void get(){
        for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
        for(int i=1;i<=n;i++)if(!vis[i])cnt++,dfs(i);
    }
}G;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int s1=0,s2=0;
        scanf("%d%d",&s1,&s2);
        G.add(s1,s2),G.add(s2,s1);
    }
    G.get();
    printf("%d\n",G.cnt);
    for(int i=1;i<=G.cnt;i++,putchar('\n')){
        printf("%u ",G.eDCC[i].size());
        for(auto j:G.eDCC[i])printf("%d ",j);
    }
    return 0;
}

原文地址：http://www.cnblogs.com/hxqasd/p/16827716.html