tarjan算法之桥

博客推荐

与割点的最大不同之处:low[v]>low[u]

易错点:

1.父亲节点与子节点区别一下,防止两个点误认为环。

2.去重边

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int maxn=10005;
int n,m;
struct node2
{
    int x,y;
} ee[maxn*maxn];
int cmp(node2 a,node2 b)
{
    if(a.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}
struct node
{
    int v,nex;
} e[maxn*maxn];
int first[maxn];
int tot,top,ans,din,cnt;
int dfn[maxn],low[maxn],Stack[maxn],in[maxn];
int son,flag[maxn];
void init()
{
    mem(first,-1);
    tot=0;
    top=0;
    din=0;
    son=0;
    ans=0;
    cnt=0;
    mem(dfn,0);
    mem(low,0);
    mem(Stack,0);
    mem(in,0);
    mem(flag,0);
}
void edge(int u,int v)
{
    e[tot].v=v;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void tarjan(int u,int vv)
{
    dfn[u]=low[u]=++din;
    Stack[top++]=u;
    in[u]=1;
    int v;
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {

        v=e[i].v;
        if(i==(vv^1)) continue;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            //printf("       %d %d\n",low[v],dfn[u]);
            if(low[v]>dfn[u])
            {
                ee[cnt].x=v;
                ee[cnt].y=u;
                if(v>u)
                    swap(ee[cnt].x,ee[cnt].y);
                cnt++;
            }
        }
        else if(in[v]&&low[u]>dfn[v])
        {
            //printf("       %d %d\n",u,v);
            low[u]=dfn[v];
        }
    }//printf("sdfa\n");
}

int main()
{
    int tt=1;
    while(~scanf("%d",&n))
    {
        if(n==0)
        {
            printf("0 critical links\n\n");
            continue;
        }
        init();
        int u,v,k;
        for(int i=0; i<n; i++)
        {
            scanf("%d (%d)",&u,&k);
            for(int j=0; j<k; j++)
            {
                scanf("%d",&v);
                int flag=0;
                for(int j=first[u]; j!=-1; j=e[j].nex)
                {
                    int qq=e[j].v;
                    if(qq==v)
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==1) continue;
                //printf("%d %d\n",u,v);
                edge(u,v);
                edge(v,u);
            }
        }
        for(int i=0; i<n; i++)
        {
            if(!dfn[i])
                tarjan(i,-1);
        }
        sort(ee,ee+cnt,cmp);
        printf("%d critical links\n",cnt);
        for(int i=0; i<cnt; i++)
        {
            printf("%d - %d\n",ee[i].x,ee[i].y);
        }
        printf("\n");
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注