Tarjan 算法之无向图

Tarjan 要素

p1.png

DFS 搜索树:即对图进行 DFS 遍历时所有递归到的边组成的树。

时间戳:对于每一个结点,我们用 DFN[i] 表示结点 i 被遍历时的次序。

追溯值:Tarjan 算法引入了追溯值 low[x].

设以 x 为根的子树为 subtree(x).

low[x] 定义为以下结点的 DFN 的最小值:(与 Tarjan 有向图中的 low[x] 区分)

  1. subtree(x) 中的结点
  2. 通过一条不在搜索树上的边能到达 subtree(x) 的结点。

不难发现,low[i] 按搜索树的递归遍历顺序是单调递增的,因此可以在回溯的过程中求出 low[i].

无向图的割点与割边

对于无向图 G 中的结点 x,如果删掉它以及与它相连的边后,整个图连通块数量增加,则结点 x 被称为无向图的割点。

对于无向图 G 中的边 (x,y),如果删掉它后,整个图连通块数量增加,则 (x,y) 被称为无向图的割边,也称作桥。

p2.png

判定割边 (x,y)

  1. 割边一定是 DFS 搜索树上的边.
  2. 令 x 是 y 的父结点,则满足 。也就是说,从 subtree(x) 出发,不经过 (x,y) 的前提下无法走到更早访问的结点,则 (x,y) 作为 subtree(x) 与图 G 的唯一连接,即为割边。
int dfn[N],low[N],dfn_cnt;
int ans[N],cnt;
void tarjan(int k,int p){//tarjan 找桥
    dfn[k]=low[k]=++dfn_cnt;
    for(int i=h[k];i;i=e[i].nex){int u=e[i].t;
        if(!dfn[u]){tarjan(u,k);
            low[k]=min(low[k],low[u]);
            if(dfn[k]<low[u])ans[++cnt]=e[i].idx;// 桥
        }
        else if(u!=p)low[k]=min(low[k],dfn[u]);
    }
}

判定割点 x

  1. 若 x 不为根结点,则要求,存在 x 的子结点 y,满足 . 即 subtree(y) 中的结点最多能走到结点 x,那么将 x 删除就会导致 subtree(y) 与图 G 不连通.
  2. 若 x 是根结点,则要求存在至少 2 个的子结点 y,满足 .
void tarjan(int u,int p){low[u]=dfn[u]=++dcnt;
    int count=0;
    for(int i=h[u];i;i=e[i].nex){const int v=e[i].t;
        if(!dfn[v]){tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v])count++;
        }
        else if(v!=p)low[u]=min(low[u],dfn[v]);
    }
    if(count-(u==p)>0)ans[++ant]=u;
}

无向图的双连通分量

p3.png

边双连通分量 ·E-DCC

无向图 G 的子图 G’内不存在割边,则称 G’是图 G 的边双连通分量。

对于图 G,直接删掉所有割边,剩下分量的就是边双连通分量。

点双连通分量 ·V-DCC

无向图 G 的子图 G’内不存在割点,则称 G’是图 G 的点双连通分量。

对于图 G,割点可能同时属于多个 v-DCC,但每一条边一定只属于一个 v-DCC.

图中通过边的不同颜色来标记 v-DCC.

求 v-DCC,需在 Tarjan 算法中维护一个栈:

  1. 当结点 x 被第一次访问时,把该结点入栈。
  2. 当割点判定条件 成立时,无论 x 是否为根:
    1. 从栈顶不断弹出结点,直到 y 被弹出。
    2. 刚才弹出的所有结点与结点 x 一起构成一个 v-DCC.

[POI2008]BLO

给定一张无向图,求每个点被封锁之后有多少个有序点对 (x,y)(x!=y,1<=x,y<=n) 满足 x 无法到达 y

分析

对于非割点,只会减少和这个点有关的 个点对

对于割点,则除上述之外,剩下的连通块之间也相应的有点对

poi2008

对于一个割点,将其连接的边删去后,剩余的连通块有三种情况(以上图 4 号点为例)

  • 割点本身(4 号点)
  • 其搜索树上的子结点为根构成的连通块(3,8 为根的搜索树构成的连通块)
  • 除上述之外的结点构成一个连通块(1,2,5,6)

于是对于结点 ,设其搜索树上的子结点为 ,以 为根的搜索树的大小为 ,那么删除 后消失的点对为

在 tarjan 的过程中统计即可

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005,M=500005;
int n,m;

struct qxx{int nex,t;};
qxx e[M*2];
int h[N],cnt;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}

int dfncnt;
int dfn[N],low[N],s[N],tp;
int sz[N];// 以 i 为根的搜索树的大小
long long ans[N];
void tarjan(int u,int p){//p 为 u 的父结点
    dfn[u]=low[u]=++dfncnt,s[++tp]=u,sz[u]=1;
    int count=0,sum=0;// 当前 u 的子结点的子树和
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
        if(!dfn[v]){tarjan(v,u);
            low[u]=min(low[u],low[v]);
            sz[u]+=sz[v];
            if(dfn[u]<=low[v]){ans[u]+=(long long)sz[v]*(n-sz[v]);// 统计答案
                sum+=sz[v],count++;//count:dfn[u]<=low[v] 的个数
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(count-(u==p)>0)ans[u]+=(long long)(n-1-sum)*(1+sum)+n-1;
    else ans[u]=2*(n-1);// 不是割点,之前的计算无效
}
int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){int a,b;
        scanf("%d%d",&a,&b);
        add_path(a,b);add_path(b,a);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,i);
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}

 上一篇
Tarjan 之有向图 SCC Tarjan 之有向图 SCC
tarjan 一直是我认为非常玄学的算法。首先不提它的描述之模糊,dalao 们写的博客之雷同。这算法的应用就很玄学。于是,本蒟蒻今天就来揭开它神秘的面纱…… Tarjan 与 DFS 生成树Tarjan 算法是由 Robert Tarja
2018.12.06
下一篇 
最短路算法 最短路算法
摘要 复习一下模板 2019.6.4:编入精选文章 图的最短路,指的是在一个加权图 G 中某两点相距的最短路程的长度(有时要求记录路径)。 严格地说,最短路分有向与无向两种。有向的最短路强调起点和终点的区别,而无向的最短路则只需要连接两点
2018.12.05
  目录