Tarjan

· · 题解

Tarjan

1.几个基本概念

点双连通分量（点双）： 无向图中的一个点导出子图，满足图连通且任意删去一个点后图仍然连通。

边双连通分量（边双）： 无向图中的一个点导出子图，满足图连通且任意删去一条边后图仍然连通。

强连通分量： 有向图中的一个点导出子图，满足任意两个点都可以互相到达。

所以，我们可以得出几个简单的小结论：

<1>这三个概念中，仅强连通分量是有向图中的概念 并且，一个点仅在一个强连通分量中

<2>每条边仅可能在一个边双中，但每个点可能在多个点双中

如下图的红点：

<3>边双不一定是点双，点双不一定是边双，点双不一定是边双 （两个点一条边）。

<4>割点：无向连通图中的点，满足删掉之后图不再连通。

<5>割边：无向连通图中的边，满足删掉之后图不再连通。

<6>割点分隔不同的点双，割边分隔不同的边双。

Tarjan用途：求 点双，边双，强连通分量

时间复杂度: O(m+n)

这三个代码仅有一些细节上的差别

进入正题

Tarjan基础算法

对整张图进行dfs，用一个栈维护dfs到的所有点，再记录一下每个点是否在栈里。 每个点维护两个信息：dfn表示dfs到这个点的顺序，low表示这个点能沿着非树边回到的dfn最小的点。 一开始令low[u]=dfn[u]，并将u压入栈。 到点u时，枚举出边(u,v)，如果没有访问到，就继续dfs点v，然后low[u]=min(low[u],low[v])。 否则，如果v当前在栈里，就令low[u]=min(low[u],dfn[v])

然后这三者有一些小区别：

强连通分量：当u的出边枚举完时，如果low[u]=dfn[u]，就说明找到了一个强连通分量，弹栈直到弹出点u为止，这些点构成一个强连通分量。

边双：当u的出边枚举完时，如果low[u]=dfn[u]，就说明找到了一个边双，弹栈直到弹出点u为止，这些点构成一个边双。然后u连向dfs树上父亲的边是一条割边。

点双：当枚举出边(u,v)并dfs点v后，如果low[v]>=dfn[u]，就说明找到了一个点双，弹栈直到弹出点v为止，这些点连同点u构成一个点双。然后如果u不是dfs的第一个点，则u是一个割点。

对于dfs的第一个点，如果不止一次遇到枚举出边并dfs下去的情况，则它是一个割点。

代码：

强连通分量

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
vector <int> q[100];
struct Edge{
    int to,nex;
}e[100100];
int num_edge,head[10010];
inline void add(int from,int to){
    e[++num_edge].to=to;
    e[num_edge].nex=head[from];
    head[from]=num_edge;
}
int dfn[100100],low[100100],st[100100],inst[100100];
int top;
int tim;
int tot;
void dfs(int now){
    dfn[now]=low[now]=++tim;
    st[++top]=now;inst[now]=1;
    for(int i=head[now];i;i=e[i].nex){
        int j=e[i].to;
        if(!dfn[j]){
            dfs(j);
            low[now]=min(low[now],low[j]);
        }else if(inst[j]){
            low[now]=min(low[now],dfn[j]);
        }
    }
    if(low[now]==dfn[now]){
        ++tot;
        int p;
        do{
            p=st[top--];
            inst[p]=0;
            q[tot].push_back(p);
        }while(p!=now);
    }
}
int main(){
    return 0;
}

边双

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
vector <int> q[100];
struct Edge{
    int to,nex;
}e[100100];
int num_edge=1,head[10010];
inline void add(int from,int to){
    e[++num_edge].to=to;
    e[num_edge].nex=head[from];
    head[from]=num_edge;
}
int dfn[100100],low[100100],st[100100],inst[100100];
int top;
int tim;
int tot;
void dfs(int now,int lst){
    dfn[now]=low[now]=++tim;
    st[++top]=now;inst[now]=1;
    for(int i=head[now];i;i=e[i].nex)if(i!=(lst^1)){
        int j=e[i].to;
        if(!dfn[j]){
            dfs(j,i);
            low[now]=min(low[now],low[j]);
        }else if(inst[j]){
            low[now]=min(low[now],dfn[j]);
        }
    }
    if(low[now]==dfn[now]){
        ++tot;
        int p;
        do{
            p=st[top--];
            inst[p]=0;
            q[tot].push_back(p);
        }while(p!=now);
    }
}
int main(){
    return 0;
}

点双

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
vector <int> q[100];
struct Edge{
    int to,nex;
}e[100100];
int num_edge,head[10010];
inline void add(int from,int to){
    e[++num_edge].to=to;
    e[num_edge].nex=head[from];
    head[from]=num_edge;
}
int dfn[100100],low[100100],st[100100],inst[100100];
int top;
int tim;
int tot;
void dfs(int now){
    dfn[now]=low[now]=++tim;
    st[++top]=now;inst[now]=1;
    for(int i=head[now];i;i=e[i].nex){
        int j=e[i].to;
            if(!dfn[j]){
                dfs(j);
                low[now]=min(low[now],low[j]);
                if(low[j]>=dfn[now]){
                    ++tot;
                    int p;
                    q[tot].push_back(now);
                    do{
                        p=st[top--];
                        inst[p]=0;
                        q[tot].push_back(p);
                    }while(p!=j);
                }
        }else if(inst[j]){
            low[now]=min(low[now],dfn[j]);
        }
    }
}
int main(){
    return 0;
}

缩点

求出强连通分量之后，我们可以把每个强连通分量直接缩成一个点，得到一张有向无环图（dag）。

为什么无环？因为一个环也是一个强连通分量，已经被缩起来了。

对于边双，我们同样也可以进行缩点，得到的是一棵树（有环的话同样被缩起来了）

有个例题 P3387 缩点

代码：

#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
vector <int> q[100];
struct Edge{
    int to,nex;
}e[100100];
int c[10010],num_edge,head[10010],a[10010];
inline void add(int from,int to){
    e[++num_edge].to=to;
    e[num_edge].nex=head[from];
    head[from]=num_edge;
}
int dfn[100100],low[100100],st[100100],inst[100100];
int top;
int tim;
int tot;
void dfs(int now){
    dfn[now]=low[now]=++tim;
    st[++top]=now;inst[now]=1;
    for(int i=head[now];i;i=e[i].nex){
        int j=e[i].to;
        if(!dfn[j]){
            dfs(j);
            low[now]=min(low[now],low[j]);
        }else if(inst[j]){
            low[now]=min(low[now],dfn[j]);
        }
    }
    if(low[now]==dfn[now]){
        ++tot;//cout<<"/////";
        int p;
        do{
            p=st[top--];
            inst[p]=0;
            q[tot].push_back(p);
            a[p]=tot;
        }while(p!=now);
    }
}
struct Node1{
    int to,nex;
}e1[100100];
int dp[100000];
int head1[10010],num_edge1;
void add1(int from,int to){
    e1[++num_edge1].to=to;
    e1[num_edge1].nex=head1[from];
    head1[from]=num_edge1;
}
int c1[10010];
int in[100010];
queue <int> in_kong;
void sd(){
    for(int i=1;i<=tot;i++){
        int ans=0;
        for(int j=0;j<q[i].size();++j){
            ans+=c[q[i][j]];
            for(int k=head[q[i][j]];k;k=e[k].nex){
                if(a[e[k].to]!=a[q[i][j]]){
                    add1(a[q[i][j]],a[e[k].to]);
                    in[a[e[k].to]]++;
                }
            }
        }
        c1[i]=ans;
    }
    for(int i=1;i<=tot;i++){
        if(in[i]==0){in_kong.push(i);dp[i]=c1[i];}
    }
}
int tuopuxv[100100],num_tuopuxv;
void topu(){
    while(!in_kong.empty()){
        int tmpi=in_kong.front();
        in_kong.pop();
        ++num_tuopuxv;
        tuopuxv[num_tuopuxv]=tmpi;
        for(int i=head1[tmpi];i;i=e1[i].nex){
            in[e1[i].to]--;
            if(in[e1[i].to]==0)in_kong.push(e1[i].to);
        }
    }
}
int n,m;

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)if(!dfn[i]){
        dfs(i);
    }
    sd();topu();
    for(int i=1;i<=tot;i++){
        int v=tuopuxv[i];
        for(int k=head1[v];k;k=e1[k].nex){
            dp[e1[k].to]=max(dp[e1[k].to],dp[v]+c1[e1[k].to]);
        }
    }
    //cout<<tot;
    int mmax=0;
    for(int i=1;i<=n;i++){
        if(mmax<dp[i])mmax=dp[i];
    }
    cout<<mmax;
    return 0;
}

未完待续。。。。。。

洛谷，有缘再见！