首页 > 代码库 > tarjian强联通分量(模板)

tarjian强联通分量(模板)

来,水水模板吧。。。。。

#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define N 10000using namespace std;int x,y,n,m,t,tot,sum,top,time;int head[N],col[N],stack[N],dfn[N],low[N],a[N][N];bool vis[N];struct Edge{    int from,next,to; }edge[N];int add(int x,int y){    tot++;    edge[tot].to=y;    edge[tot].next=head[x];    head[x]=tot;}int read(){    int x=0,f=1; char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return f*x;}int tarjian(int now){    t=0;    dfn[now]=low[now]=++time;//初始每一个点的low值dfn等于它的时间戳     stack[++top]=now; vis[now]=true;//将该点入栈,标记为在栈中     for(int i=head[now];i;i=edge[i].next)//更新于他相连的点的low值     {        x=edge[i].to;        if(vis[x]) low[i]=min(dfn[x],low[i]);//如果该点已经在栈中         else if(!dfn[x])        {            tarjian(x);            low[i]=min(low[x],low[i]);//从该点继续拓展         }    }    if(low[now]==dfn[now])//说明以这个点结束强连通分量     {        sum++;// 强连通分量的个数加一         col[now]=sum;//将该点放在她所属的强连通分量了         for(;stack[top]!=now;top--)        {            col[stack[top]]=sum;            vis[stack[top]]=false;        }        vis[now]=false;        top--;     } }int main(){    n=read(),m=read();    for(int i=1;i<=m;i++)     {         x=read();y=read();         add(x,y);     }    for(int i=1;i<=n;i++)      if(!dfn[i]) tarjian(i);    printf("%d",sum);    return 0;}

 

tarjian强联通分量(模板)