tarjan解惑

benny · 2021-09-01 07:08:43 · 个人记录

如果你感觉tarjan算法很玄，如果你对其似懂非懂，本篇题解很适合你

小白转 https://zhuanlan.zhihu.com/p/101923309

误区1：强连通分量（SCC)内所有节点的low值相等，均为同一顶点（即该SCC最浅点，也称割点)的dfn
误区2：当搜索到x时，栈内点均为x祖先
误区3：如下写法是不对的：

if (vis[v])  low[x]=min(low[x],low[v]);

而必须写教材上的

if (vis[v])  low[x]=min(low[x],dfn[v]);

误区4:


if (vis[v])  low[x]=min(low[x],dfn[v]);

if条件判定可以省略，直接写

```c
 low[x]=min(low[x],dfn[v]);

下文中，我将对以上误区作说明

一、震惊！两个tarjan

误区3是对算法的刻板理解，事实上，两个tarjan都是对的，它们的搜索过程、栈处理、dfn处理无任何区别，但low值有微妙差别 (不用担心，如果用dfn[x]==low[x]作出栈判定条件是无影响的)

注意学习中辨别张冠李戴的论述

二、栈的意义

两个tarjan有相同的栈处理，栈是low的前提

预告一下，该栈非常玄学，不一定是链，也不一定包含什么SCC，很像是各个SCC假肢拼凑到一起（ ~~这么血腥的吗~~）

先搞清楚SCC在搜索树里的形态。如果u是v的祖先，并且u和v互通(即属于同一个SCC)，那么u到v的每一个点都属于同一个SCC。换言之，如果v可以到达它的老祖先u，那么v的年轻祖先也可以到达u。（~~你叫你爷爷为”儿子“，你爸就可以叫他“孙子”了~~）
那么，SCC在搜索树里的形态，很像是你往树中的某一结点（顶点）注射胶水，胶水顺着枝干向叶子延伸，流到某一处（不一定是叶子）停止。即，搜索树的子树按特定方式剪枝后的树
那么，如果搜索到x，栈的意义是什么呢？设先序遍历小于x（即dfn小于dfn[x])的点集为S，S减去S内所有的SCC，即为栈元素集
包含但不仅限于x的祖先

三、low与low'的意义

首先声明，他们都很复杂：同一个SCC中的点，low值不一定相同,low'值也不一定相同。如果x不是顶点，那么问x的low或者low'，几乎是没有意义的
万幸的是，当x是顶点时,low与low'意义相同。它们都是dfn[x]
所以这个问题不能一个点一个点地看，不能一条边一条边地看，得一个顶点一个顶点地看，得一座桥一座桥地看，得一棵树一颗树地看，得一个SCC一个SCC地看
怎么看呢？设现在搜索到了顶点x，那么就有两个点集：一是栈元素集S，二是以x为顶点的scc
scc能直接到达的点中，有一部分属于s。这一些点的最小dfn，即为low[x]或low'[x]或dfn[x]
算法好像在对顶点x说：你用你的SCC来够一够栈元素呀？够不到你就是真的顶点喽
反之,若考虑y在scc里但y不是顶点x，则low[y]一定小于dfn[x]。因为y既然能直接或间接地抵达它的祖先x，则一定会触碰到（搜索到y时的）栈元素（具体怎么触碰就不需要管了）

四、栈判定的必要性

来解答误区4，如果没有vis判定，搜索到顶点x时，会怎么样呢？

算法就变成说：你用你的SCC来随便摸？管它栈不栈，摸到了你就犯法，你就不是顶点
x会很冤："怎么我往下摸也犯法？"

五、吐槽一下

似乎tarjan可解释性质并不好，很奇怪为什么不用深度而用dfn和low，求大佬解答。不管怎样，附代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL maxLL=1e15;
const LL maxn=2e4;
const LL maxm=2e5;
int n,i,j,L,k,m,x,t,c,y;
int a[maxn],v[maxn],f[maxn];
int hea[maxn],poi[maxm],nex[maxm];
int HEA[maxn],POI[maxm],NEX[maxm];
int low[maxn],dfn[maxn],col[maxn];
int sta[maxn];
deque<int> q;

void PW(int i,int j)
{
    if(i==j) return;
    x++; poi[x]=j; nex[x]=hea[i];hea[i]=x;
}

int top(){return sta[sta[0]];}
void push(int x){sta[++sta[0]]=x;f[x]=1;}
void pop(){f[top()]=0;sta[0]--;}

void tj(int c,int from)
{
    //printf("tj %d %d\n",c,f[7]);
    k++; dfn[c]=low[c]=k;
    push(c);
    int i,y;
    for(i=hea[c];i;i=nex[i])
    {
        y=poi[i];
        if(dfn[y])
        {
            if(f[y]) 
                low[c]=min(low[c],dfn[y]);
        }else
        {
            tj(y,c);
            low[c]=min(low[c],low[y]);
        }
    }
    if(low[c]==dfn[c])
    {
        //printf("%d\n",c);
        col[0]++;
        while(top()!=c) col[top()]=col[0], pop();
        col[top()]=col[0],pop();
    }
}
void SD()
{
    k=0;
    for(i=1;i<=n;i++)
        if(dfn[i]==0)
            tj(i,0);/*
    for(i=1;i<=n;i++)
        printf("%d dfn=%d col=%d low=%d\n",
        i,dfn[i],col[i],low[i]);*/
    x=0;
    for(i=1;i<=n;i++)
        v[col[i]]+=a[i];
    for(i=1;i<=n;i++)
    {
        for(j=hea[i];j;j=nex[j])
            POI[j]=poi[j],
            NEX[j]=nex[j];
        HEA[i]=hea[i],hea[i]=0;
    }
    x=0;
    for(i=1;i<=n;i++)
        for(j=HEA[i];j;j=NEX[j])
            PW(col[i],col[POI[j]]);
    n=col[0];

}
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&j,&t);
        PW(j,t);
    }
    SD();/*
    for(i=1;i<=n;i++)
    {
        printf("%d v=%d:\n",i,v[i]);
        for(j=hea[i];j;j=nex[j]) printf("%d ",poi[j]);
        printf("\n");
    }*/
    memset(a,0,sizeof(a));
    memset(f,0,sizeof(f));
    for(i=1;i<=n;i++)
        for(j=hea[i];j;j=nex[j])
        {
            a[poi[j]]++;

        }
    for(i=1;i<=n;i++) if(a[i]==0) q.push_back(i),f[i]=v[i];
    while(!q.empty())
    {
        c=q.front(); q.pop_front();
        //printf(":%d\n",c);
        for(i=hea[c];i;i=nex[i])
        {
            y=poi[i];
            f[y]=max(f[y],f[c]+v[y]);
            a[y]--;
            if(a[y]==0)
                q.push_back(y);
        }
    }
    for(i=1;i<=n;i++) f[0]=max(f[0],f[i]);
    printf("%d",f[0]);

}