tarjan 算法及其应用

红火恍惚cxy · 2022-08-16 00:05:47 · 个人记录

tarjan 算法及其应用

0.前言

tarjan 算法，听名字也能知道，又是 tarjan 他老人家发明的。以他的名字命名的算法很多，我们这里要介绍的是在有向图中求强连通分量的 Tarjan 算法。

算法并不复杂，但思想及应用还算广泛，今天在这里总结一下。

1.问题

先来看我们的问题：
【模板】缩点

看到这个题，我们可以想到用 dp 解决。
但是，单纯的一张有向图，是不满足我们的无后效性的。比如：

在这张图中，我们对 1 更新答案的时候，需要知道 3 的答案，但事实上 3 的答案我们需要知道 2 的答案后才能求出，所以这并不满足 dp 所需要的无后效性。

那什么样的图才满足我们所需要的无后效性呢？

我们发现，在这张图中，1、2、3、5 这4个点是可以任意两两到达的。也就是说只要我们走到了其中一个点，其他点我们一定可以到达，之后再回到当前点。

像这样一组可以两两互相到达的点，我们称之为一个强连通分量。贴一下强连通分量的定义：

“有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。”

那我们是不是可以把它们 4 个点缩在一起，看成一个大点呢？

所以上面的图我们可以把它变成这样：

对于所有的有向图，都可以把其中可以互相走到的点缩在一起，即把强连通分量缩在一起，这样我们就会得到一张新图。在这张图上，任意两个点均无法互相走到，即原图所有强连通分量都是一个单独的点，这张图也就是一个有向无环图。
而在有向无环图上，是满足我们的无后效性的。

之后在这张无后效性的图上，我们就可以按照拓扑序，愉快的跑 dp 了 qwq。

所以我们现在的问题是，怎么找强连通分量呢？

2.有向图缩点

我们先来看看有向图中的情况。

（一张朴实无华的有向图

边的分类

我们想得到一张图上的信息，最朴实无华的方法不过是 DFS 了。
我们从 1 号点开始通过 DFS 遍历整张图，只要图是连通的，一定会依次经过每一个点。
如果我们在经过每一个点的时候，记录下它是第几个被我们经过的点，这样所有点就都被我们按照一定顺序记录了下来。
这个顺序叫做 DFS 搜索序。我们将每个点经过的次序记作这个点的 dfn 值，也可以叫做这个点的时间戳。

这时候，我们来看看我们走过的是哪几条边。

蓝色的是我们经过的边。
如果将其他的边全部去掉，这张图其实就变成一棵树了，这棵树我们把它叫做搜索树。所以我们可以把它叫做树边。

再看看其他的边，有没有什么共同之处。
其实可以发现它们分为三种。

黄色的叫做返祖边。这条边指向自己的祖先，即根节点到自己的路径上所有的点。
红色的叫做前向边。即指向自己的孩子，即自己子树中的所有点。
绿色的叫做横插边。即指向祖先的另一棵子树中的节点。

我们可以这样理解这 4 种边：

树边是引领我们向更深的地方前进的，所有的树边构成的一定是一个有向无环图，即一棵搜索树。
前向边是引领我们向已经搜索过的更深的地方前进的，很明显这样的边并不会构成强连通分量。
返祖边是引领我们走向自己祖先的，而自己的祖先也一定可以走到自己，因此返祖边会形成强连通分量，我们需要考虑。
横插边是引领我们去到另一棵子树，而这棵子树一定是已经遍历过的，因为如果没有被遍历，那这条边就是树边了。而这课子树也一定无法到达现在所处的这课子树，否则这条边就应该是返祖边了。因此这种横插边也不会构成强连通分量，我们可以不考虑它。比如下图中的 (3,2) 这条边。

但是也有一种情况我们是需要考虑横插边的，如下图：

这里的 2 号点和 1 号点是在同一个强连通分量里的，即通过 2 可以走到 1，所以此时 (3,2) 构成了强连通分量，我们需要考虑它。

点的分类

我们再来看看经过这 4 种边，点又可以分成哪些情况：

我们记录下从每个点开始，可以到达的 dfn 序最小的节点（包括自己），将这个节点的 dfn 值记录下来，记作原来节点的 low 值。
这样一来，对于每个强连通分量，我们可以在 dfn 值最小的节点记录它，这样可以避免错算和漏算。

之后每个节点可以分成两种情况：

low 值小于 dfn 值。即可以到达自己所处的强连通分量中更小的节点，这时候我们什么也不需要做。
low 值等于 dfn 值。即自己就是这个强连通分量中最小的节点，此时我们记录下这个强连通分量就好了，怎么记录一会再说 qwq。

low 值计算

我们先来看看怎么计算 low 值。

比较明显，这玩意又是一个 dp。

欸，不是说不满足无后效性，没法进行 dp 嘛？
~~（开始套娃~~

我们这里用了一个比较巧妙的办法。我们记录的 low 值并不是可以到达的所有节点 dfn 的最小值，这是无法 dp 求出的。这里的 low 值是以下节点的 dfn 的最小值；

自己子树中的节点。
通过 1 条不在搜索树上的边（返祖边或第二种横插边），能够到达的点。

看出来了嘛，这里的区别在于我们只考虑经过 1 条边到达的点，并不考虑它所能到达的最小值是多少。即，对于一条边我们只用指向点的 dfn 值来更新当前点的 low 值，所以在我们求当前节点的 low 值时不需要知道指向节点的 low 值，因此这个 dp 是满足无后效性的。

但这样更新出来的 low 值并不是我们想要的所有可到达节点的最小值，这样怎么保证正确性呢？

对于这张图，4号点可以到达的编号最小的点为 1，而根据 low 的计算方法，4 号点在只经过一条返祖边时，low 值会被更新为 2。
可以发现，虽然并不是我们想要的 1，但通过一条返祖边或第二种横插边，我们一定可以走到一个比自己编号更小的点，这样就已经可以说明这个点不是该强连通分量的最小编号节点了，所以并不影响结果。

现在的问题是，在知道一个点是最小节点后，我们如何找到整个强连通分量？

在我们搜索的时候，所有的点访问的顺序满足先进后出，即后访问的节点一定会先被返回，利用这一点性质，我们可以利用栈来保存我们访问到的节点。

另一个性质是，强连通分量的访问在栈中一定是连续的。不可能存在我们先访问了强连通分量 A，之后抵达强连通分量 B，在强连通分量 B，返回之前，又访问到强连通分量 A 的情况。所以利用这一点，我们可以在每次找到一个强连通分量最小节点时，不断弹栈直到这个节点，这样就可以处理到所有强连通分量中的节点了。

我们来总结一下，展开一个节点时，入栈，更新 dfn 值，访问出边，更新 low 值，判断是否为最小节点，返回。更新 low 值利用下面的规则：

自己子树中的节点。
```
d[x].low=min(d[x].low,d[t[i].ver].low)
```
通过 1 条不在搜索树上的边（返祖边），能够到达的点。
```
d[x].low=min(d[x].low,d[t[i].ver].dfn)
```
(这里判断是不是返祖边有个小技巧，记录一下一个节点是否在栈中即可，或判断这个点是否被打上了已有的强连通分量标记)

部分代码：

inline void dfs(int x){
    d[x].low=d[x].dfn=++cnt;
    s.push(x);
    for(int i=d[x].hed;i;i=t[i].nxt){
        if(d[t[i].ver].dfn==0){//树边
            dfs(t[i].ver);
            d[x].low=min(d[x].low,d[t[i].ver].low);
        }
        if(d[t[i].ver].ver==0)//返祖边，即没有被打上强连通分量的标记
        d[x].low=min(d[x].low,d[t[i].ver].dfn);
    }
    if(d[x].dfn==d[x].low){//一个强连通分量的编号最小的节点
        ++cncnt;
        while(s.empty()==0&&s.top()!=x){
            d[s.top()].ver=cncnt;
            dd[cncnt].val+=d[s.top()].val;
            s.pop();
        }
        d[x].ver=cncnt;
        dd[cncnt].val+=d[x].val;//把点缩在一起，贡献要加起来
        s.pop();
    }
    return;
}
int main(){
    for(int i=1;i<=n;++i){
        if(d[i].dfn==0) dfs(i);
    }
    for(int i=1;i<=m;++i){
        if(d[t[i].fver].ver!=d[t[i].ver].ver){//如果一条边连接两个强连通分量，建边
            crr(d[t[i].fver].ver,d[t[i].ver].ver);
        }
    }
}

这样在配合上拓扑序进行 dp，就可以解决这个问题了。

 for(int i=1;i<=cncnt;++i){
        dd[i].ans=dd[i].val;
        if(dd[i].rd==0){
            q.push(i);
        }
    }
    while(q.empty()==0){
        x=q.front();
        q.pop();
        for(int i=dd[x].hed;i;i=tt[i].nxt){
            dd[tt[i].ver].rd--;
            dd[tt[i].ver].ans=max(dd[tt[i].ver].ans,dd[x].ans+dd[tt[i].ver].val);
            if(dd[tt[i].ver].rd==0) q.push(tt[i].ver);
        }
    }
    int ans=0;
    for(int i=1;i<=cncnt;++i){
        ans=max(ans,dd[i].ans);
    }

2.割点与桥

在无向图中，tarjan 算法依旧能发挥它的作用。

无向图必然是没有强连通分量的概念了，但有点双连通分量和边双连通分量。

在一张连通的无向图中，对于两个点 x 和 y，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 x 和 y 边双连通。

在一张连通的无向图中，对于两个点 x 和 y，如果无论删去哪个点（只能删去一个，且不能删 x 和 y 自己）都不能使它们不连通，我们就说 x 和 y 点双连通。

有了它俩的定义，就有了割点和桥。

对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。
人话：删去割点原图不连通。

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。
人话：删去桥后原图不连通。

这俩玩意怎么求呢？

桥：

一条边 (x,y) 是桥，当且仅当 x 的 dfn 值小于 y 的 low 值。

割点：

一个点 x 是割点当且仅当搜索树上 x 的一个子节点 y 满足 x 的 dfn 值小于等于 y 的 low 值。特别的是对于根节点的判断，根节点是割点需要至少有两个子节点满足条件。

贴一下求割点代码：

void dfs(ll x,bool rt)
{
    q.push(x);
    d[x].v=1;
    d[x].dfn=++tot;
    d[x].low=tot;
    for(int i=d[x].hed;i;i=t[i].nxt)
    {
        if(d[t[i].ver].v==0)
        {
            dfs(t[i].ver,0);
            if(d[x].dfn<=d[t[i].ver].low&&d[x].cut==0)
            {
                if(rt==1) rt=0;//对根节点的特殊判定
                else
                {
                    d[x].cut=1;
                    ans++;
                }

            }
            d[x].low=min(d[x].low,d[t[i].ver].low);
        }
        else
        if(d[t[i].ver].v==1) d[x].low=min(d[x].low,d[t[i].ver].dfn);
    }
    return;
}

3.题目

【模板】缩点
【模板】割点（割顶）
The Cow Prom S
最受欢迎的牛
BLO
Network of Schools

4.补充 2-SAT

来看这样一道题目：
【模板】2-SAT 问题

对于这个问题，我们需要做的就是在众多限制下，确定每个点是 1 还是 0。

观察每个条件，比如 a 为假或 b 为假，其实可以换一种理解方式：

如果 a 为真，则 b 为假；
如果 b 为真，则 a 为假。

这样就把一个条件拆成了两个依赖关系。

还记得关押罪犯嘛？这里用到了类似的思想。
我们这里将一个点拆成两个，分别代表该点选择为真还是为假。

对于每个依赖关系，我们进行连边，表示前一个条件满足，后一个条件一定需要满足。

当我们对所有的条件进行处理之后，得到的就是一张有向图了。
这时我们对每个点进行判断：

如果从真点出发，走不到假点，并且从假点出发走不到真点，说明这个点为真和为假不存在依赖关系，所以不影响结果，随便选一个就好了。
如果从真点出发，能走到假点，并且从假点出发走不到真点，说明选择真点会发生矛盾，我们只能选择假点。
如果从真点出发，走不到假点，并且从假点出发能走到真点，说明选择假点会发生矛盾，我们只能选择真点。
如果从真点出发，能走到到假点，并且从假点出发也能走到真点，说明选择真点假点都会发生矛盾，说明无解。

那么如何判断他们之间能否相互走到呢？我们可以利用强连通分量缩点，缩点完成之后形成一张有向无环图。在这张图上我们按照拓扑序标记每个强连通分量，会有如下性质：

同一个强连通分量里的点能互相走到；
不同强连通分量里的点一定不能互相走到；
从标号大的点出发一定走不到标号小的点；
从标号小的点出发可能走到标号大的点。所以我们对每个点的真点假点编号比较，相同的话无解，不同的话选择较大的那个，一定满足要求。

所以我们只需要缩点求拓扑序就好了。
这里有一个小技巧，我们计算强连通分量时打上的标记，其实就是按照反向的拓扑序进行的，因为我们按照搜索树的顺序展开和返回，拓扑序大的强连通分量会被我们先返回，所以我们只需要利用这个标号计算即可，不需要再次进行拓扑排序。

部分代码：

inline void dfs(int x){
    d[x].dfn=d[x].low=++cnt;
    s.push(x);
    for(int i=d[x].hed;i;i=t[i].nxt){
        if(d[t[i].ver].dfn==0){
            dfs(t[i].ver);
            d[x].low=min(d[x].low,d[t[i].ver].low);
        }
        else if(d[t[i].ver].ver==0) d[x].low=min(d[x].low,d[t[i].ver].dfn);
    }
    if(d[x].dfn==d[x].low){
        ++cncnt;
        while(s.empty()==0&&s.top()!=x){
            d[s.top()].ver=cncnt;
            s.pop();
        }
        d[x].ver=cncnt;
        s.pop();
    }
    return;
}
int main(){
    for(int i=1;i<=m;++i){
        x=read();
        a=read();
        y=read();
        b=read();
        cr(a==0?x:x+n,b==0?y+n:y);
        cr(b==0?y:y+n,a==0?x+n:x);
    }
    for(int i=1;i<=2*n;++i){
        if(d[i].dfn==0) dfs(i);
    }
    for(int i=1;i<=n;++i){
        if(d[i].ver==d[i+n].ver){
            printf("IMPOSSIBLE");
            return 0;
        }
        ans[i]=d[i].ver<d[i+n].ver?1:0;
    }
}

放几道题目：

[NOI2017] 游戏
[JSOI2010] 满汉全席

5.参考资料

初探tarjan算法（求强连通分量）
T a r j a n，你真的了解吗？
60 分钟搞定图论中的 Tarjan 算法（一）