2017-team2/vertice-tarjan

从 Trac 迁移的文章

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

原文章内容如下：

{{{
void addedge(int x,int y)
{
    edge[++top].adj=y;
    edge[top].next=gh[x];
    edge[top].f=1;
    gh[x]=top;
}
void dfs(int x)
{
    for(int p=gh[x];p;p=edge[p].next)
        if (edge[p].f==1)
        {
            edge[p].f=0;
            edge[p^1].f=0;
            node t; t.x=x; t.y=edge[p].adj;
            s.push(t);
            if (!v[edge[p].adj])
            {
                v[edge[p].adj]=1;
                ++ind;
                dfn[edge[p].adj]=ind;
                low[edge[p].adj]=ind;
                dfs(edge[p].adj);
                low[x]=min(low[x],low[edge[p].adj]);
                if (low[edge[p].adj]>=dfn[x])
                {
                    cnt++;
                    a[cnt].clear();
                    while (1)
                    {
                        node temp;
                        temp=s.top();
                        s.pop();
                        a[cnt].pb(temp);
                        //printf("%d-%d ",temp.x,temp.y);
                        if((temp.x==edge[p].adj&&temp.y==x)||(temp.x==x&&temp.y==edge[p].adj))break;
                    }
                   if (a[cnt].size()==1)cnt--;
                   //puts("");
                }
            }
            else low[x]=min(low[x],dfn[edge[p].adj]);
        }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)gh[i]=0; 
    top=1;
    for(int i=1;i<=m;i++)
    {
        int x,y; scanf("%d%d",&x,&y);
        addedge(x,y); 
        addedge(y,x);
    }
    cnt=ind=0;
    for(int i=1;i<=n;i++)dfn[i]=v[i]=0;
    for(int i=1;i<=n;i++)
        if (!v[i])
        {
            v[i]=1;
            low[i]=dfn[i]=++ind;
            dfs(i);
        }
}
}}}

void addedge(int x,int y)
{
    edge[++top].adj=y;
    edge[top].next=gh[x];
    edge[top].f=1;
    gh[x]=top;
}
void dfs(int x)
{
    for(int p=gh[x];p;p=edge[p].next)
        if (edge[p].f==1)
        {
            edge[p].f=0;
            edge[p^1].f=0;
            node t; t.x=x; t.y=edge[p].adj;
            s.push(t);
            if (!v[edge[p].adj])
            {
                v[edge[p].adj]=1;
                ++ind;
                dfn[edge[p].adj]=ind;
                low[edge[p].adj]=ind;
                dfs(edge[p].adj);
                low[x]=min(low[x],low[edge[p].adj]);
                if (low[edge[p].adj]>=dfn[x])
                {
                    cnt++;
                    a[cnt].clear();
                    while (1)
                    {
                        node temp;
                        temp=s.top();
                        s.pop();
                        a[cnt].pb(temp);
                        //printf("%d-%d ",temp.x,temp.y);
                        if((temp.x==edge[p].adj&&temp.y==x)||(temp.x==x&&temp.y==edge[p].adj))break;
                    }
                   if (a[cnt].size()==1)cnt--;
                   //puts("");
                }
            }
            else low[x]=min(low[x],dfn[edge[p].adj]);
        }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)gh[i]=0; 
    top=1;
    for(int i=1;i<=m;i++)
    {
        int x,y; scanf("%d%d",&x,&y);
        addedge(x,y); 
        addedge(y,x);
    }
    cnt=ind=0;
    for(int i=1;i<=n;i++)dfn[i]=v[i]=0;
    for(int i=1;i<=n;i++)
        if (!v[i])
        {
            v[i]=1;
            low[i]=dfn[i]=++ind;
            dfs(i);
        }
}