hdu4612 无向图中任意添加一条边后使桥的数量最少 / 无向图缩点+求树的直径

题意如上，含有重边（重边的话，俩个点就可以构成了边双连通）。

先缩点成树，在求数的直径，最远的连起来，剩下边（桥）的自然最少。这里学习了树的直径求法：第一次选任意起点U，进行bfs，到达最远的一个点v（level最深）该点必然是树的直径的一个端点，,再从该点出发，bfs，到最深的一点，该点深度就是直径。（证明：先假设u，是直径上一点，S,T是直径的端点，设v!=t,则有（V,U)+(U,S)>(T,U)+(U,S),矛盾，故t=v；若u不是直径上一点，设u到直径上的一点为x，同理易证。

最后缩点后树的边-直径即可。

再说说这次，哎，先是爆栈，没有在C++申请空间。。。无向图的tarjian太不熟练了！很久没敲了。。。。

注意点：无向图求边双连通，缩点，可以这样：

法1：必需用前向星来保存边，然后标记访问边（同时标记反向边）的方法来处理。这样，重边的话，就在字自然在一个边通分量中了。（要求边数可以用数组存下），这样不用！=-father来判断。

法2，重边视为单边（只有俩个点不连通），不标记边，多一个参数father，在返祖边更新我的时候，加判断！=father。

#pragma comment(linker, "/STACK:10240000000000,10240000000000")        //申请空间

#include<iostream>

#include<vector>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<stack>

using namespace std;

const int maxv=300010;

int dfn[maxv];int low[maxv];int visited[maxv];

int ins[maxv];stack<int>sta;int scc[maxv];

int times=0;int block=0;

int n,m;

int minn(int a,int b)

{

    if(a<=b)return a;

    return b;

}

int nume=0;int e[2000500][2];int head[maxv];

void inline adde(int i,int j)                 //原图

{

    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume++;

    e[nume][0]=i;e[nume][1]=head[j];head[j]=nume++;

}

int nume2=0;int newg[2000500][2];int head2[maxv];

void inline adde2(int i,int j)                //新图

{

    newg[nume2][0]=j;newg[nume2][1]=head2[i];head2[i]=nume2++;

    newg[nume2][0]=i;newg[nume2][1]=head2[j];head2[j]=nume2++;

}

bool marke[2001000];          //标记边的访问

void tarjan(int u)

{

    dfn[u]=low[u]=++times;

    ins[u]=1;

    sta.push(u);

    for(int i=head[u];i!=-1;i=e[i][1])

    {

        int child=e[i][0];

         if(marke[i])continue;            //注意放在这里，否则下面的会更新，起不了作用

        if(visited[child]==0)

        {

            visited[child]=1;

            marke[i]=marke[i^1]=1;       //标记双向

            tarjan(child);

            low[u]=minn(low[u],low[child]);

        }

        else if(ins[child])

        {

            low[u]=minn(dfn[child],low[u]);

        }

   }

    if(low[u]==dfn[u])          //同一个边双连通

   {

       block++;

       int cur;

       do

       {

           cur=sta.top();

           ins[cur]=0;

           sta.pop();

           scc[cur]=block;

       }while(cur!=u);

   }

}

void rebuild()

{

    for(int i=1;i<=n;i++)             //遍历所有边，来重新建图，若在同一个边双连通中，则有边。

    {

        for(int j=head[i];j!=-1;j=e[j][1])

        {

             int ch=e[j][0];

            if(scc[i]!=scc[ch])

                 adde2(scc[i],scc[ch]);

        }

    }

}

int lev[maxv];

void bfsgetlev(int ss)               //BFS分层

{

    memset(lev,0,sizeof(lev));

    memset(visited,0,sizeof(visited));

    queue<int>q;

    q.push(ss);

    visited[ss]=1;

    while(!q.empty())

    {

        int cur=q.front();

        q.pop();

        for(int i=head2[cur];i!=-1;i=newg[i][1])

        {

            int vv=newg[i][0];

             if(!visited[vv])

             {

                 lev[vv]=lev[cur]+1;

                 q.push(vv);

                 visited[vv]=1;

             }

        }

    }

    return ;

}

void init()

{

          block=times=0;nume=0;nume2=0;

          memset(marke,0,sizeof(marke));

          memset(dfn,0,sizeof(dfn));

          memset(low,0,sizeof(low));

          memset(visited,0,sizeof(visited));

          memset(head,-1,sizeof(head));

          memset(head2,-1,sizeof(head2));

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))

     {

         init();

        int a,b;

        for(int i=0;i<m;i++)

        {

           scanf("%d%d",&a,&b);

             adde(a,b);

        }

        visited[1]=1;

        tarjan(1);

        rebuild();

          int ans=0;

             bfsgetlev(1);

            int froms=0;

           int maxx=-1;

            for(int i=1;i<=block;i++)

            {

                if(lev[i]>maxx)

                {

                    maxx=lev[i];

                    froms=i;

                }

            }

             bfsgetlev(froms);                   //最远点（直直径的一个端点）

            for(int i=1;i<=block;i++)

            {

                if(lev[i]>maxx)

                {

                    maxx=lev[i];

                }

            }

              ans=block-1-maxx;

            printf("%d\n",ans);

      }

       return 0;

}

巴特西

hdu4612 无向图中任意添加一条边后使桥的数量最少 / 无向图缩点+求树的直径

最新文章

热门文章