强连通分量的模版 Kosaraju+Tarjan+Garbow

　　PS：在贴出代码之前，我得说明内容来源——哈尔滨工业大学出版的《图论及应用》。虽然有一些错误的地方，但是不得不说是初学者该用的书。

　　从效率的角度来说，Kosaraju <Tarjan<Garbow。一般网上有前两种的代码和分析。Garbow算法是Tarjan的另一种实现，但是Garbow效率更高。

　　不过从复杂度来说，三种算法的时间（空间）复杂度都是O(m +n)。

　　模版的调用方式很简单，初始化，建图，调用Tarjan(n)或者Kosaraju(n)或者 Garbow(n)， scc就是强连通分量的个数。

（1）Kosaraju

//Kosaraju

const int N =, M=;

struct node

{

    int to, next;

}edge[M],edge2[M]; //edge是逆图,edge2是原图

int  dfn[N], head[N], head2[N],  belg[N], num[N];

//dfn时间戳

//belg记录每个点属于哪个连通分量,num记录强连通分量点的个数

bool  vis[N];

int cnt,cnt1,scc,tot,tot1;

void dfs1(int u)

{

    vis[u]=;

    for(int k=head2[u];k!=-;k=edge2[k].next)

        if(!vis[edge2[k].to]) dfs1(edge2[k].to);

    dfn[++cnt1]=u;

}

void dfs2(int u)

{

    vis[u]=;

    cnt++;

    belg[u]=scc;

    for(int k=head[u];k!=-;k=edge[k].next)

        if(!vis[edge[k].to]) dfs2(edge[k].to);

}

void  Kosaraju(int n)

{

    memset(dfn,,sizeof(dfn));

    memset(vis,,sizeof(vis));

    cnt1=scc=;

    for(int i=;i<=n;i++)

        if(!vis[i]) dfs1(i);

    memset(vis,,sizeof(vis));

    for(int i=cnt1;i>;i--)

        if(!vis[dfn[i]])

        {

            cnt=;

            ++scc;

            dfs2(dfn[i]);

            num[scc] = cnt;

        }

}

void init()

{

    tot=tot1=;

    memset(head,-,sizeof(head));

    memset(head2,-,sizeof(head2));

    memset(num,,sizeof(num));

}

void addedge(int i,int j)

{

    edge2[tot1].to=j; edge2[tot1].next=head2[i];head2[i]=tot1++;

    edge[tot].to=i; edge[tot].next=head[j];head[j]=tot++;

}

(2)Tarjan

//Tarjan

const int N =, M=;

struct node

{

    int to, next;

}edge[M];

int head[N], low[N], dfn[N], sta[N], belg[N], num[N];

bool vis[N];

int scc,index,top, tot;

void tarbfs(int u)

{

    int i,j,k,v;

    low[u]=dfn[u]=++index;

    sta[top++]=u;

    vis[u]=;

    for(i=head[u];i!=-;i=edge[i].next)

    {

        v=edge[i].to;

        if(!dfn[v])

        {

            tarbfs(v);

            if(low[u]>low[v]) low[u]=low[v];

        }

        else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v];

    }

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

    {

        scc++;

        do

        {

            v=sta[--top];

            vis[v]=;

            belg[v]=scc;

            num[scc]++;

        }

        while(v!=u) ;

    }

}

void Tarjan(int n)

{

    memset(vis,,sizeof(vis));

    memset(dfn,,sizeof(dfn));

    memset(num,,sizeof(num));

    memset(low,,sizeof(low));

    index=scc=top=;

    for(int i=;i<=n;i++)

        if(!dfn[i]) tarbfs(i);

}

void init()

{

    tot=;

    memset(head,-,sizeof(head));

}

void addedge(int i,int j)

{

    edge[tot].to=j; edge[tot].next=head[i];head[i]=tot++;

}

(3)Garbow

//Garbow

const int N =, M=;

struct node

{

    int to, next;;

}edge[M];

int stk[N],stk2[N],head[N],low[N],belg[N];

int cn,cm,tot,scc,lay;

int Garbowbfs(int cur,int lay)

{

    stk[++cn]=cur; stk2[++cm]=cur;

    low[cur]=++lay;

    for(int i=head[cur];i!=-;i=edge[i].next)

    {

        int v=edge[i].to;

        if(!low[v]) Garbowbfs(v,lay);

        else if(!belg[v])

            while(low[stk2[cm]]>low[v]) cm--;

    }

    if(stk2[cm]==cur)

    {

        cm--;

        scc++;

        do

            belg[stk[cn]]=scc;

        while(stk[cn--]!=cur) ;

    }

    return ;

}

void Garbow(int n)

{

    scc=lay=;

    memset(belg,,sizeof(belg));

    memset(low,,sizeof(low));

    for(int i=;i<n;i++)

        if(!low[i]) Garbowbfs(i,lay);

}

void init()

{

    memset(head,-,sizeof(-));

}

void addedge(int i,int j)

{

    edge[tot].to=j; edge[tot].next=head[i];head[i]=tot++;

}

巴特西

强连通分量的模版 Kosaraju+Tarjan+Garbow

最新文章

热门文章