强连通图和双连通图

刚刚弄明白了强连通和双连通，我好菜啊。。TUT

两道差不多的题目，POJ – 3177  和计蒜客的Islands

poj-3177 给出很多边，问添加最少多少条边成为一个双连通

Islands 变成强连通

强连通：图中任意两个节点可以相互通达

双连通：图中任意两个节点之间都有两条路

POJ-3177 跑一遍Tarjan 所有的双连通块看做一个点，将整个图看做一棵树，把整棵树的叶子节点连接起来，就是答案了。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5123;
struct node
{
    int v,next;
    bool cut;
} eage[N*10];
int head[N];
int dfn[N],low[N],Belong[N];
int du[N],Instack[N];
int Stack[N];
int tot;
int Index,top;
int block;
int n,m;
void Add(int u,int v)
{
    eage[top].v=v;
    eage[top].cut=0;
    eage[top].next=head[u];
    head[u]=top++;
}
void Tarjan(int u,int pre)
{
    dfn[u]=low[u]=++Index;
    Instack[u]=1;
    Stack[tot++]=u;
    for(int i=head[u]; i!=-1; i=eage[i].next)
    {
        int v=eage[i].v;
        if(v==pre)continue;
        if(!dfn[v])
        {
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
            {
                eage[i].cut=1;
                eage[i^1].cut=1;
            }
        }
        else if(Instack[v]&&low[u]>dfn[v])
        low[u]=dfn[v];
    }
    int v;
    if(low[u]==dfn[u])
    {
        block++;
        do
        {
            v=Stack[--tot];
            Instack[v]=0;
            Belong[v]=block;
        }
        while(v!=u);
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(head,-1,sizeof(head));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(Belong,0,sizeof(Belong));
        memset(Instack,0,sizeof(Instack));
        memset(Stack,0,sizeof(Stack));
        memset(du,0,sizeof(du));
        Index=top=tot=0;
        block=0;
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            Add(u,v);
            Add(v,u);
        }
        Tarjan(1,0);
        for(int u=1; u<=n; u++)
        {
            for(int i=head[u]; i!=-1; i=eage[i].next)
            {
                if(eage[i].cut)
                    du[Belong[u]]++;//将所有的双连通看做一个点
            }
        }
        int ans=0;
        for(int i=1; i<=block; i++)
        {
            if(du[i]==1)ans++;//叶子节点
        }
        printf("%d\n",(ans+1)/2);
    }
    return 0;
}

Islands 和双连通有一点区别，将所有强连通块看做一个点，最后统计入度为0的点和出度为0的点，取最大值

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=11234;
const int M=112345;
struct node
{
    int v,next;
    bool cut;
} eage[N*10];
int head[N];
int dfn[N],low[N],Belong[N];
int du[N],Instack[N];
int Stack[N];
int In[N];
int Out[N];
int tot;
int Index,top;
int block;
int n,m;
void Add(int u,int v)
{
    eage[top].v=v;
    eage[top].cut=0;
    eage[top].next=head[u];
    head[u]=top++;
}
void Tarjan(int u,int pre)
{
    dfn[u]=low[u]=++Index;
    Instack[u]=1;
    Stack[tot++]=u;
    for(int i=head[u]; i!=-1; i=eage[i].next)
    {
        int v=eage[i].v;
        if(v==pre)continue;
        if(!dfn[v])
        {
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
            {
                eage[i].cut=1;
                eage[i^1].cut=1;
            }
        }
        else if(Instack[v]&&low[u]>dfn[v])
        low[u]=dfn[v];
    }
    int v;
    if(low[u]==dfn[u])
    {
        block++;
        do
        {
            v=Stack[--tot];
            Instack[v]=0;
            Belong[v]=block;
        }
        while(v!=u);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(Belong,0,sizeof(Belong));
        memset(Instack,0,sizeof(Instack));
        memset(Stack,0,sizeof(Stack));
        memset(du,0,sizeof(du));
        memset(In,0,sizeof(In));
        memset(Out,0,sizeof(Out));
        Index=top=tot=0;
        block=0;
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            Add(u,v);
            //Add(v,u);
        }
        int u,i;
        for(i=1;i<=n;i++)
        {
            if(!dfn[i])Tarjan(i,i);
        }
        for(u=1;u<=n;u++)
        {
            for(i=head[u];i!=-1;i=eage[i].next)
            {
                int v=eage[i].v;
                if(Belong[v]!=Belong[u])
                {
                    In[Belong[v]]++;//相当于把它们建一个图？
                    Out[Belong[u]]++;
                }
            }
        }
        int in=0,out=0;
        for(i=1;i<=block;i++)
        {
            if(!In[i])in++;
            if(!Out[i])out++;
        }
        if(block==1)printf("%d\n",0);
        else printf("%d\n",max(in,out));//找出最大值
    }
    return 0;
}

今天的文章强连通图和双连通图分享到此就结束了，感谢您的阅读。