『图连通性问题的Tarjan算法』

2022-11-15 20:59:39

本文不会涉及算法原理。

无向图Tarjan算法

割点和割边

对于无向联通图\(\mathrm{G=(V,E)}\)，定义：

若点\(x\in\mathrm{V}\)，从图中删去节点\(x\)以及所有与其相连的边后，图\(\mathrm{G}\)分裂为两个或两个以上不连通的子图，则称\(x\)为图\(\mathrm{G}\)的割点
若点\(e\in\mathrm{E}\)，从图中删去边\(e\)后，图\(\mathrm{G}\)分裂为两个不连通的子图，则称\(e\)为图\(\mathrm{G}\)的割边

一般无向图的割点和割边就是每个连通块的割点和割边。

对于割边，我们有明确的\(\mathrm{Tarjan}\)算法可以在\(\mathcal{O}(n)\)的时间内解决，思路是遍历无向图的搜索树，通过割边判定法则\(\mathrm{dfn}_x<\mathrm{low}_y\)进行判定，代码如下：

inline void Tarjan(int x,int ine)
{
    dfn[x] = low[x] = ++tot;
    for (int i = Head[x] , y; i; i = e[i].next)
        if ( !dfn[ y = e[i].ver ] ) Tarjan(y,i) , low[x] = min( low[x] , low[y] ),
            ( dfn[x] >= low[y] ?: cut[i] = cut[i^1] = 1 );
        else if ( i != ( ine ^ 1 ) ) low[x] = min( low[x] , dfn[y] );
}

对于割点，涉及到点双联通分量的若干细节事宜影响，此处先不作讲解。

边双联通分量

边双联通图是一个定义在无向联通图上的概念，定义有两种：

对于一个无向联通图，若任意两点间都存在至少两条不重复经过一条边的路径，则称该图是一个边双连通图
对于一个无向联通图，若其不存在割边，则称该图是一个边双连通图

两个定义完全等价。

一个无向联通图是边双联通图，当且仅当任意一条边都被包含在至少一个简单环中。

对于一个一般的无向图，称其极大边双联通子图为它的一个边双联通分量，一个无向联通图可能有多个边双联通分量。

对于一般的无向图，我们使用\(\mathrm{Tarjan}\)算法求出其所有桥并将其删去之后，所得的各个连通块就是原图的边双联通分量。将边双联通分量缩为一个点，原图将会变为一棵树，代码容易实现，不再赘述。

点双联通分量

点双联通图是一个及其容易误解的概念，其定义也有两种：

对于一个无向联通图，若任意两点间都存在至少两条不重复经过一个点的路径，则称该图是一个点双连通图（不考虑起点终点）
对于一个无向联通图，若其不存在割点，则称该图是一个点双连通图

对于这两种定义那个是真正被承认的，存在较大的争议，因为对于一个点的图和两点中间仅有一条边的图，我们难以确定其到底是不是点双连通图。

根据定义\(2\)，点数\(|\mathrm{V}|\leq2\)的图都应该是点双连通图，但是根据定义\(1\)不是。

还有一种说法：点数\(|\mathrm{V}|\leq2\)的图也符合定义\(1\)，因为不考虑起点终点的情况下路径确实可以认为没有重复经过一个点。

比较好的理解方式是承认上述说法成立，这样两个定义就完全等价了，下文也都将以这种方式来理解点双。

同样的，对于一个一般的无向图，称其极大点双联通子图为它的一个点双联通分量，一个无向联通图可能有多个点双联通分量。

值得注意的是，一个无向图的点双联通分量不是删去割点后原图的各个连通块，相反，任意两个点双联通分量的交集就是割点，换言之，一个割点可能属于多个点双。

判定一个无向联通图是点双连通图，当且仅当满足以下两个条件之一：

\(1.\) \(|\mathrm{V}|\leq 2\)
\(2.\) 图中任意两点至少被包含在至少一个简单环中

我们有可以求解割点和点双的\(\mathrm{Tarjan}\)算法，但是鉴于割点和点双的特殊性，此处不推荐使用，下文会介绍用\(\mathrm{Tarjan}\)求解圆方树的算法。

圆方树

对于一个无向联通图，有且仅有一棵确定的圆方树，其点数为\(n+c\)，\(c\)为原图点双联通分量个数。

对于原图的每一个点双联通分量，我们建立\(c\)个虚拟点，称其为方点，方点向原图中属于该点双的每一个点连一条边，构成的树称为圆方树，原图中的点在圆方树中称为圆点。

下图为\(\mathrm{WC2018}\ \mathrm{immortalCO}\)课件中的图。

圆方树具有以下几个性质：

没有任何圆点或者方点会直接相邻。
若一个圆点连接两个或以上个数的方点，则该圆点为这些方点所代表点双的交集，同时也说明该圆点为割点，换言之，圆方树上所有非叶子圆点都是割点。
原图中点\(a,b\)所有简单路径的并集就是圆方树上圆点\(a,b\)路径上所有方点代表点双的并集。

使用无向图的\(\mathrm{Tarjan}\)算法，我们可以在\(\mathcal{O}(n)\)的时间内构造圆方树。具体来说，我们遍历无向图的搜索树，并用栈存下当前访问的点，若某次访问儿子时满足\(\mathrm{dfn}_x=\mathrm{low}_y\)，则取出栈中的点，向新建的方点连边，代码实现如下：

inline void Tarjan(int x)
{
    dfn[x] = low[x] = ++tot , st[++top] = x;
    for (int i = Head[x] , y; i; i = e[i].next)
        if ( !dfn[ y = e[i].ver ] ) {
            Tarjan(y) , low[x] = min( low[x] , low[y] );
            if ( low[y] != dfn[x] ) continue; ++cnt;
            for (int z = 0; z != y; top--)
                E[ z = st[top] ].Push(cnt) , E[cnt].Push(z);
            E[x].Push(cnt) , E[cnt].Push(x);
        } else low[x] = min( low[x] , dfn[y] );
}

上述代码中，我们采用点双的第二定义，但是不考虑孤立点的情况。所以，我们将两个点中间连一条边看做一个点双，但是孤立点不看做点双，所以使用圆方树解题时要额外注意点数小于等于\(2\)的情况。

那么无论是割点问题还是点双问题，都有更好的解决方案了。

有向图Tarjan算法

强联通分量

对于一个有向图，若对于任意两个点\(x,y\)，都存在互相可达的路径，则称该有向图为强连通图。

对于一个有向图，称其极大强联通子图为它的强连通分量，一个有向图可能有多个强联通分量。

\(\mathrm{Tarjan}\)算法同样可以通过遍历流图的搜索树来求解有向图的强连通分量，具体来说，记录每个节点的时间戳和追溯值，并将节点存在一个栈里，在回溯时，若有\(\mathrm{dfn}_x=\mathrm{low}_x\)，则将栈顶所有\(x\)以上的节点弹出，记录为同一个强连通分量。原理是每个强连通分量在搜索树上必有一个最浅的节点，满足\(\mathrm{dfn}_x=\mathrm{low}_x\)，时间复杂度\(\mathcal{O}(n)\)，代码实现如下：

inline void Tarjan(int x)
{
    dfn[x] = low[x] = ++tot , st[++top] = x , ins[x] = true;
    for (int i = Head[x] , y; i; i = e[i].next)
        if ( !dfn[ y = e[i].ver ] ) Tarjan(y) , low[x] = min( low[x] , low[y] );
        else if ( ins[y] ) low[x] = min( low[x] , dfn[y] );
    if ( dfn[x] != low[x] ) return void(); ++cnt; int y;
    do ins[ y = st[top--] ] = 0 , c[y] = cnt; while ( x ^ y );
}

将有向图的所有强连通分量缩为一个点，保留剩下的有向边，可以得到一个有向无环图（\(\mathrm{DAG}\)），缩点的实现方法较为简单，不再赘述。

码农公寓