tarjan之双连通图(无向图)

这里有几个点需要注意
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;

struct node
{
    int u,v,nex;
} e[maxn*maxn];
int first[maxn];
int tot;
int n,m;
int ans,din,top;
int dfn[maxn],low[maxn],Stack[maxn],in[maxn];
int belong[maxn];
void init()
{
    mem(first,-1);
    tot=0;
    din=1;
    ans=0;
    top=0;
    mem(dfn,0);
    mem(low,0);
    mem(Stack,0);
    mem(in,0);
    mem(belong,0);
}
void edge(int u,int v)
{
    e[tot].u=u;
    e[tot].v=v;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void tarjan(int u,int id)
{
    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==(id^1))
            continue;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])
        {
            low[u]=min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        ans++;
        do
        {
            v=Stack[--top];
            in[v]=0;
            belong[v]=ans;
            //printf("%d\n",ans);
        }
        while(v!=u);
    }
}
void scc()
{
    for(int i=1; i<=n; i++)
    {
        if(!dfn[i])
            tarjan(i,-1);
    }
    //printf("%d\n",ans);
    int sum=0;
    int k=0;
    int aa[maxn],gg[maxn];
    mem(aa,0);
    mem(gg,0);
    for(int i=0; i<tot; i+=2)
    {
        int u=e[i].u;
        int v=e[i].v;
        if(belong[u]!=belong[v])
        {
            //printf("%d %d\n",belong[u],belong[v]);
            aa[belong[u]]++;
            aa[belong[v]]++;
        }
    }
    for(int i=1; i<=ans; i++)
    {
        if(aa[i]==1) sum++;
    }
    printf("%d\n",(sum+1)/2);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=0; i<m; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
//            int flag=0;
//            for(int j=first[u]; j!=-1; j=e[j].nex)
//            {
//                int to=e[j].v;
//                if(v==to)
//                {
//                    flag=1;
//                    break;
//                }
//            }
//            if(flag==1) continue;
            edge(u,v);
            edge(v,u);
        }
        scc();
    }
}

 

发表评论

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