Tarjan算法

· · 个人记录

Tarjan算法

写在前面

本篇笔记介绍Tarjan算法在求强连通分量（有向图）和求割点与桥以及双连通分量（无向图）中的运用。

前置知识：DFS树

DFS是在一张图中从任意结点出发按DFS的顺序建成的树，并记录每个结点i的DFS序dfn[i]

如图所示，这是一棵DFS树

显然，DFS树中不能包含所有的边，除了DFS树中的树边以外，还有以下几种边：

强联通分量

定义： 强联通分量（SCC）是指在一张有向图中，满足任何结点互相均可达的极大的子图

在有向图中，可以通过Tarjan算法在O(n+m)的复杂度中求出其中所有的强联通分量

Tarjan算法中通过维护每个结点的low[]值处理问题

结点i的low[i]定义为：在DFS树中，结点i通过其子树中的结点能回溯到的 dfn[]最小的 结点

如图所示，以图中的树为例，每个结点的dfn[i] 和 low[i]用点对表示

我们使用栈维护每一个SCC（处于当前SCC的结点都在栈中），将处理完的SCC中的结点出栈（这点下文会讲解决方法）

对于low[]的处理，可以根据以下方法，通过一遍DFS的回溯过程实现：

记当前结点u，其出边通往的为v，分类讨论：

  1. 若v未被访问过，则边(u,v)是树边（例如图中5 \to 6），low[u]=min(low[u],low[v])，u可能通过v回溯到更早的结点

  2. 若v已被访问且仍在栈中（不在栈中的结点已经处理完了），则该边为非树边（例如图中6 \to 4），low[u]=min(low[u],dfn[v])

进一步思考，我们可以发现，对于一个结点x，若是满足dfn[x]=low[x]，那么此节点就是它属于的SCC中的第一个结点

这是因为满足该条件的结点x的子树中的任何结点都只能最多回溯到x，因此x一定是SCC中的第一个结点。

所以，若是在一次回溯完成后，发现满足dfn[x]=low[x]，则不断弹出栈中结点，直到弹出了结点x

由于栈先进后出的性质，此时栈中在结点x之上的结点都是x的子树中的结点，它们一定是此SCC中的点（例如上图中结点1）

找出SCC的代码如下：

inline void Tarjan(int x)
{
    dfn[x]=low[x]=++now,stk[++top]=x,fl[x]=1;//fl[]标记结点是否在栈中
    for(int i=H1[x];i;i=G1[i].next)
    {
        int v=G1[i].v;
        if(!dfn[v]) Tarjan(v),low[x]=min(low[v],low[x]);//情况1
        else if(fl[v]) low[x]=min(low[x],dfn[v]);//情况2
    }
    if(dfn[x]==low[x])
    {
        cnt++;//SCC个数加1
        while(1)
        {
            scc[stk[top]]=cnt;//标记栈中结点属于当前SCC
            siz[cnt]++;//siz[i]：第i个SCC的大小，不断累加
            fl[stk[top]]=0;
            top--;
            if(stk[top+1]==x) break;//当x被弹出时结束
        }
    }
}

应用：缩点

通过对有向图中的SCC的处理，我们可以将整张图进行缩点

缩点就是将图中的SCC缩成一个点（因为其中的点互相可达），来将原图变成一张DAG（有向无环图），以进行拓扑排序等操作

具体进行缩点操作时，对于原图中的一条边u\to v，若有：scc[u]\neq scc[v]，则在新图（缩点图）中建一条scc[u]\to scc[v]的边

代码如下：

  for(int i=1;i<=tot1;i++)
    if(scc[G1[i].u]!=scc[G1[i].v])
    {
      int x=scc[G1[i].u],y=scc[G1[i].v];
      Add2(x,y);
    }

习题：【模板】缩点

割点与桥

通过Tarjan算法在无向图中的运用，我们还可以求出无向图中所有的割点与桥

割点： 删除当前点使得无向图的连通块个数增加，则该点被称为割点

桥： 删除当前边使得无向图的连通块个数增加，则该点被称为桥（割边）

对于一个点u以及它的一个子结点v，若是满足：dfn[u]\le low[v]，则u为割点。

在DFS树中，若是想要从u的子树中回到u的祖先，必须经过结点u ，所以删除u必然会使连通块数量增加

同理，对于一条u\to v的有向边，若是满足：dfn[u]<low[v]，则该边为桥

需要注意的是，无向图中的DFS树是有向的，即不走回头路。

同时，对于DFS树的树根需要特判，若是root有两个以上子树，那么它也是割点

求割点的代码如下，求桥同理：

inline void Tarjan(int x)
{
    dfn[x]=low[x]=++tot;
    for(int i=0;i<G[x].size();i++)
    {
        int v=G[x][i];
        if(!dfn[v]) 
        {   
            Tarjan(v);
            if(x==root) son++;
            else
            {
                low[x]=min(low[x],low[v]);
                if(low[v]>=dfn[x]) cut[x]=1;//标记割点
            }
        }
        else low[x]=min(low[x],dfn[v]);
    }
    if(x==root && son>1) cut[x]=1;//特判树根
}

【模板】割点

双连通分量

处理了无向图中的割点与桥，我们可以求出无向图中的每一个双连通分量

双连通分量包括点-双连通分量（以下简称点双） 和 边-双连通分量（以下简称边双）

点-双连通分量： 一个满足每个结点与其他所有结点至少有2条点不重复的路径的连通分量

边-双连通分量： 一个满足每个结点与其他所有结点至少有2条边不重复的路径的连通分量

以下分别介绍两种双连通分量的求解方法。

点-双连通分量

有一个重要的结论：点双内部没有任何割点

若是有割点，割点两端的结点的路径必然经过割点，不符合定义。

与求SCC的方法类似，使用栈维护DFS时经过的结点，若是发现结点x为割点，那么不断出栈并将栈中结点加入点双，最后将结点x也加入点双

代码如下：

inline void Tarjan(int x,int fa)
{
    low[x]=dfn[x]=++tot,stk[++top]=x;
    int son=0;
    for(int i=H[x];i;i=G[i].next)
    {
        int v=G[i].v;
        if(!dfn[v])
        {
            son++;
            Tarjan(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x])//若x为割点
            {
                cnt++;
                while(stk[top+1]!=v) bcc[cnt].push_back(stk[top--]);//不断加入当前点双
                bcc[cnt].push_back(x);//加入x
            }
        }
        else if(v!=fa) low[x]=min(low[x],dfn[v]);
    }
    if(fa==0 && son==0) bcc[++cnt].push_back(x);//特判孤立点，自己就是点双
}

边-双连通分量

边双与点双类似，有结论：边双内没有桥

结论的证明一样，此处不加赘述

于是我们可以朴素的想：通过Tarjan算法找出所有的桥后，将这些桥删除，剩下的连通块就一定是边双了

求出桥的代码如下：

//此处有一个trick，将每条边从2开始编号
//那么设当前边编号为i，无向图中i的反边为i^1
inline void Tarjan(int x,int fa)//fa为连接x的上一条边
{
    dfn[x]=low[x]=++amt;
    for(int i=H[x];i;i=G[i].next)
    {
        int v=G[i].v;
        if(!dfn[v])
        {
            Tarjan(v,i);
            low[x]=min(low[v],low[x]);
            if(dfn[x]<low[v]) cut[i]=cut[i^1]=1;//标记桥
        }
        else if(i!=(fa^1)) low[x]=min(low[x],dfn[v]);
    }
}

标记桥之后，求出每个连通块的代码如下：

inline void Search(int x,int id)//id为结点x所属的边双
{
    belong[x]=id,bcc[id-1].push_back(x);//加入当前结点
    for(int i=H[x];i;i=G[i].next)
    {
        int v=G[i].v;
        if(cut[i] || belong[v]) continue;//桥不能走，通往的结点未被处理
        Search(v,id);
    }
}

【模板】点双连通分量

【模板】边双连通分量