2017-team2/edge-tarjan

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
#define N 500010
#define M 2000010
struct EDGE {int adj,next; } edge[M];
int n,m,top,gh[N];
int dfn[N],low[N],cnt,ind,stop,instack[N],stck[N],belong[N];

void addedge(int x,int y)
{
    edge[++top].adj=y;
    edge[top].next=gh[x];
    gh[x]=top;
}
void Tarjan(int x,int pre)
{
    dfn[x]=low[x]=++ind;
    instack[x]=1; stck[++stop]=x;
    for(int p=gh[x];p;p=edge[p].next)
        {
                if (edge[p].adj==pre)continue;
        if (!dfn[edge[p].adj])
        {
            Tarjan(edge[p].adj,x);
            low[x]=min(low[x],low[edge[p].adj]);
        }else if (instack[edge[p].adj])
        {
            low[x]=min(low[x],dfn[edge[p].adj]);
        }
        }
    if (dfn[x]==low[x])
    {
        ++cnt; int tmp=0;
        while (tmp!=x)
        {
            tmp=stck[stop--];
            belong[tmp]=cnt;
            instack[tmp]=0;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)gh[i]=0; 
    top=stop=cnt=ind=0;
    for(int i=1;i<=m;i++)
    {
        int x,y; scanf("%d%d",&x,&y);
        addedge(x,y);
                addedge(y,x);
    }
    for(int i=1;i<=n;i++)dfn[i]=0;
    for(int i=1;i<=n;i++)
        if (dfn[i]==0)Tarjan(i,0);
    return 0;
}




}}}

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
#define N 500010
#define M 2000010
struct EDGE {int adj,next; } edge[M];
int n,m,top,gh[N];
int dfn[N],low[N],cnt,ind,stop,instack[N],stck[N],belong[N];
void addedge(int x,int y)
{
    edge[++top].adj=y;
    edge[top].next=gh[x];
    gh[x]=top;
}
void Tarjan(int x,int pre)
{
    dfn[x]=low[x]=++ind;
    instack[x]=1; stck[++stop]=x;
    for(int p=gh[x];p;p=edge[p].next)
        {
                if (edge[p].adj==pre)continue;
        if (!dfn[edge[p].adj])
        {
            Tarjan(edge[p].adj,x);
            low[x]=min(low[x],low[edge[p].adj]);
        }else if (instack[edge[p].adj])
        {
            low[x]=min(low[x],dfn[edge[p].adj]);
        }
        }
    if (dfn[x]==low[x])
    {
        ++cnt; int tmp=0;
        while (tmp!=x)
        {
            tmp=stck[stop--];
            belong[tmp]=cnt;
            instack[tmp]=0;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)gh[i]=0; 
    top=stop=cnt=ind=0;
    for(int i=1;i<=m;i++)
    {
        int x,y; scanf("%d%d",&x,&y);
        addedge(x,y);
                addedge(y,x);
    }
    for(int i=1;i<=n;i++)dfn[i]=0;
    for(int i=1;i<=n;i++)
        if (dfn[i]==0)Tarjan(i,0);
    return 0;
}