Tarjan学习笔记

-1 前言

许久不见，甚是思念。

0 前置芝士

• 图论相关基础知识

• DFS

1 什么是Tarjan

TarganTarjan是一位计算机科学家，全名Robert Tarjan（中文一般译为罗伯特·塔扬）。现在常说的Tarjan一般指Tarjan发明的，以他自己命名的算法。

这个算法可以用于求一个有向图中的SCC，同时其拓展出的很多的方法也用于缩点，割点，割边等问题。

2 一些定义

• 强连通：如果一个图中的节点两两可达，则称这张图是强连通的。

• 强连通分量（SCC）：一个图中的极大强联通子图。

待补。

3 原理

本文以下所述内容均以 洛谷B3609 为例。

Tarjan算法的核心，在于巧妙的将一个图和其DFS搜索树巧妙的联系起来。

举个例子，对于下面这样一个有向图，我们对其进行DFS得到一颗搜索树。

不难发现，搜索树中的每条边都是有向图中的边，而有向图中的边却有一些没有添加到搜索树中。如果我们把剩下的边添加进去，会怎样呢？

我们可以把所有边分成四种：

• 树边：即搜索树上原有的边。

• 返祖边：从子节点向祖先节点的边；

• 前向边：从祖先节点向子节点的边（不包括父节点向子节点的边）。

• 横叉边：从一个点到既不是其祖先，也不是其子树的节点的边。

通过观察不难发现，加入返祖边后必然出现强连通子图，加入横叉边如果配合返祖边则有可能出现强连通子图，而加入前向边则没有贡献。

并且，观察发现，用 $top_i$ 表示结点 $i$ 可以通过横叉边或返祖边到达的 $dfn$ 最小点的 $dfn$，那么一个SCC里所有点的 $top_i$ 是相同的。

Tarjan算法接下来的思路是用一个栈维护当前节点能拓展到的没有访问的节点。为了方便，我们将一个SCC中第一个访问到，即 $dfn$ 最小的节点称为该SCC的根。

接下来的思路就很明了了。在遍历的过程中，遍历到第 $i$ 个点先将其入栈，然后扩展到与其相邻的点。

• 若该点没有被访问过，那么遍历这个点，并且遍历完成后用这个点的 $top$ 值更新 $top_i$。

• 若该点被访问过并且在栈中，那么说明这个点与 $i$ 属于同一SCC，用这个点的 $top$ 值更新 $top_i$ 。

• 若该点属于其他SCC，即被访问过且不在栈中，那么该点对于当前SCC一定没有贡献，不需要操作。

4 具体实现

题目要求我们输出SCC的个数以及包含的节点编号，因此我们可以在一个SCC处理完成之后来储存当前SCC的答案。

需要注意的是，在本题中，题目要求按照每个SCC的根的数值大小升序输出，每个SCC中的点也要升序输出。

具体代码如下：

//上面是冗长的缺省源
int n,m;
vector<int> g[N];
int dfn[N],tp[N];
bool vis[N];
vector<int> scc[N];
int cnt;
stack<int> st;
int ans=0;
void targan(int x){
    dfn[x]=tp[x]=++cnt;vis[x]=1;st.push(x);
    for(auto &i:g[x]){
        if(!dfn[i]){
            targan(i);
            tp[x]=min(tp[x],tp[i]);
        }elif(vis[i]){tp[x]=min(tp[x],tp[i]);}
    }
    if(dfn[x]==tp[x]){
        ans++;
        int tmp=0;
        do{
            tmp=st.top();st.pop();
            vis[tmp]=0;
            scc[x].push_back(tmp);
        }while(tmp!=x);//注意不能清空栈，而是要记录到当前SCC的根为止
    }
}
vector<pair<int,int>> num;//记录每个SCC输出的顺序
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        g[u].push_back(v);
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i])targan(i);
    }
    for(int i=1;i<=n;++i){
        sort(scc[i].begin(),scc[i].end());
        if(!scc[i].empty()){
            num.push_back(make_pair(scc[i][0],i));
        }
    }
    sort(num.begin(),num.end());
    printf("%lld\n",ans);
    for(int i=0;i<ans;++i){
        for(auto &j:scc[num[i].second])printf("%lld ",j);
        printf("\n");
    }
    return 0;
}

5 后记

长时间后的又一篇。

我大概是回来了，我大概是回不去了。