强联通分量（tarjan算法+算法简介）

时间：2023-03-09 15:38:18
强联通分量（tarjan算法+算法简介）

题目描述

›对于一个有向图顶点的子集S，如果在S内任取两个顶点u和v，都能找到一条从u到v的路径，那么就称S是强连通的。如果在强连通的顶点集合S中加入其他任意顶点集合后，它都不再是强连通的，那么就称S是原图的一个强连通分量（SCC: Strongly Connected Component）。任意有向图都可以分解成若干不相交的强连通分量，这就是强连通分量分解。把分解后的强连通分量缩成一个顶点，就得到了一个DAG（有向无环图）。
现在，请求一个有向图中强连通分量的个数

输入

第一行两个数V，E，表示顶点数和边数

接下来E行，两个数s，t，描述一条有向边

输出

强连通分量的个数

求强联通分量当然可以暴力，不过慢一些

今天我们讲讲tarjan算法（更快解决您的需求哦=￣ω￣=）

首先我们需要2个数组，1个数组是时间戳（dns），用于判断某点是否是某强联通分量的起点

另一个数组是low，用于记录某点属于哪一个强联通分量。

在我们遍历每个点时，初始状态就是dns[i]=low[i]=++tot;//tot为目前遍历点的编号

接下来我们利用链表寻找下一个点

如果这个点还未被访问那么我们就访问他tarjan(g[i].to);

如果我们已经访问了这个点，那我们判断一下它是否在栈内（没错！tarjan算法利用的就是栈）

如果在栈内（如果不在栈内那么不属于一个强联通分量，不用更新low数组），则更新low数组（保证low数组最小）low[i]=min(low[i],low[g[i].to]);

最后我们判断一下如果low[i]=dns[i]即该点为此次查找的强连通分量的起点

然后我们查找在它之后进栈的元素，让他们出站，答案+1；

当然，有些图不只一个连通图

所以我们要每一个点都遍历一遍，如果没有便历过，那么就进行tarjan

由于每一个点都进栈一次，出栈一次

所以最坏复杂度为O（n+m）

下面贴代码（终于打完了。。手残。。）

#include<cstdio>

inline int read()

{

    int x=;char c;

    while((c=getchar())<''||c>'');

    for(;c>=''&&c<='';c=getchar())x=x*+c-'';

    return x;

}

#define MN 10000

#define MM 50000

struct edge{int nx,t;}e[MM+];

int h[MN+],en,d[MN+],l[MN+],cnt,z[MN+],zn,inz[MN+],K;

inline void ins(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;}

void tj(int x)

{

    d[x]=l[x]=++cnt;inz[z[zn++]=x]=;

    for(int i=h[x];i;i=e[i].nx)

    {

        if(!d[e[i].t])tj(e[i].t);

        if(inz[e[i].t]&&l[e[i].t]<l[x])l[x]=l[e[i].t];

    }

    if(d[x]==l[x])for(++K;z[zn]!=x;)inz[z[--zn]]=;

}

int main()

{

    int n,m,i;

    n=read();m=read();

    while(m--)i=read(),ins(i,read());

    for(i=;i<=n;++i)if(!d[i])tj(i);

    printf("%d",K);

}

下面贴代码

相关文章