对强连通分量tarjan算法的思考

对强连通分量tarjan算法的思考

最近做最短路题目的时候突然乱入一个强连通分量题目,开始还奇怪,以为是标签标错了,后来发现用强连通分量来做属于杀鸡用牛刀——数据很小,暴搜即可。但是还是回顾了一下tarjan算法。
唉,本来都打得很熟了,现在几个月没动全忘了,GG。
所以就打开洛谷网校的最新讲义,找到了关于tarjan的部分(没错,这是自愿写的广告,因为我喜欢洛谷XD),看一遍基本就想起来了,但这次我的目标是深入理解,以便以后不用花这么长时间复习。
其中比较核心的一部分内容是:

if(!dfn[j])
{
    tarjan(j);
    if(low[j]<low[i])low[i]=low[j];
}
else if(low[i]>dfn[j]&&ins[j])low[i]=dfn[j];

这里更新了low[i],但是和low[i]比较的值并不一样,一个是low[j],另一个是dfn[j],这个应该是有原因的,不然tarjan就直接都写成low[j]了。
于是就脑洞大开画了这个图:

在这个图上,更新low[4]的时候会与dfn[2]=2比较并赋值,但是这时low[2]=1,记得某大佬曾说过这里写什么都一样,本着这个思路,我开始找原因。
最终,我发现,low的值改变只是为了判断这个强连通分量中的点都已经进入栈中,只要使low[i]与dfn[i]不同就可以了,所以low[i]=dfn[j]可以改成low[i]=low[j]。
但是tarjan前辈为啥要写成dfn呢?
dfn想刷一下存在感?认为只要值不一样就可以所以随便写了一个?留给后人思考坑他们?…(以上本人脑洞)
这个要问tarjan前辈自己了…
最后附上强连通分量的代码以及上面的图的测试数据:

//目测强连通分量tarjan找环+对剩下的边排序并输出。 
//然而忘记了tarjan怎么写...尴尬
#include<bits/stdc++.h>
using namespace std;
const int maxn=1001,maxm=50001;
int n,m,dfn[maxn],low[maxn],stap[maxn],stop=0,index=0,top=0,ins[maxn],bcnt=0,f,g,head[maxn],belong[maxn];
struct node
{
    int to,next;
}edge[maxm];
inline void addedge(int x,int y)
{
    edge[++top].next=head[x];
    head[x]=top;
    edge[top].to=y;
    return;
}
void tarjan(int i)
{
    int j;
    dfn[i]=low[i]=++index;
    stap[++stop]=i;ins[i]=1;
    for(int o=head[i];o;o=edge[o].next)
    {
        j=edge[o].to;
        if(!dfn[j])
        {
            tarjan(j);
            if(low[j]<low[i])low[i]=low[j];
        }
        else if(low[i]>dfn[j]&&ins[j])low[i]=dfn[j];
    }
    if(dfn[i]==low[i])
    {
        ++bcnt;
        do
        {
            j=stap[stop--];
            ins[j]=0;
            belong[j]=bcnt;
        }while(j!=i);
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)ins[i]=dfn[i]=low[i]=0;
    while(m--)
    {
        scanf("%d%d",&f,&g);
        addedge(f,g);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    printf("共有%d个强连通分量\n",bcnt);
    do
    {
        for(int i=1;i<=n;i++)if(belong[i]==bcnt)printf("%d ",i);
        printf("\n");
    }while(bcnt--);
    return 0;
} 
/*测试数据
6 7
1 2
2 3
3 4
4 5
5 1
4 2
3 6
*/