tarjan 学习记

1.强连通分量是什么

强连通分量指的是部分点的集合如果能够互相到达（例如 1→3,3→2,2→1（有向图）这种，132每个点都能互相抵达）

或者说，有一个环，环上点的集合就是一个强连通分量

2.那怎么实现呢？

1.根据这个定义，容易想到的就是枚举每个环，虽然确可以得到环，但是时间复杂度趋近于O（n^3）[复杂度自己算的可能不准确]

2.优化：类似于SPFA，当每个点的入度小于进队次数的时候，跳出，外加一个数组存当前点的来源

3.O（n^2+m）算法得到每个点的遍历序，然后反向遍历，有交集的部分就是一个强连通分量

4.O（n+m）算法： tarjan，kosaraju (貌似还有一个算法和tarjan有异曲同工之妙）

前两种应该好写但是没必要写，真的有用的就是tarjan和kos算法，但是kos是跑的两遍bfs，常数比较大，所以学了tarjan

比如这张图，求他的强连通分量个数

    low[u]=++ds;

    dfn[u]=low[u];

    s.push(u);

    int i,j;

    ins[u]=;

    for(i=head[u];i;i=e[i].next)

    {

        j=e[i].to;

        if(!dfn[j])

        {

        tarjan(j);

        low[u]=min(low[u],low[j]);

        }

        else if(ins[j]) low[u]=min(low[u],dfn[j]);

    }

首先找到一个没有被访问的点（比如1）

然后从1开始遍历，dfn[i]不仅标记了i是否被访问[0或者有值]，同时标记这个点被访问的序号（留着日后作对比），右边绿色的是当前栈的情况

low表示从该店遍历能够找到的最小被访问的序号，如果往下没有边的话dfn[i]=low[i]

当现在找到了6这个点不能刷新low，因此不难发现{6}是一个强连通分量

if(dfn[u]==low[u])

    {

        cnt++;

        while(u!=j)

        {

            j=s.top();

            s.pop();

            ins[j]=;

            bd[j]=cnt;

        }

    }

于是6退栈，然后发现u==j 即6==6，跳出，然后重复这样做，发现{5}也是个强连通分量

回到3，发现还没找完边，跳到4，发现4与1联通，又可以得到low[1]]=1回溯发现low[3]=1

然后走剩下一条边，同理，发现low[1]=low[2]=low[3]=low[4]

if(dfn[u]==low[u])

    {

        cnt++;

        while(u!=j)

        {

            j=s.top();

            s.pop();

            ins[j]=;

            bd[j]=cnt;

        }

    }

于是u!=j一直做下去，的到剩下的强连通分量{1,2,3,4}

对了这道题在我发在洛谷上了：

https://www.luogu.org/problemnew/show/T84034

巴特西

tarjan 学习记

最新文章

热门文章