hdu-4612-Warm up(边双连通分量--有重边)

题意：有N 个点，M条边，加一条边，求割边最少。（有重边）

分析：先求双连通分量，缩点形成一个生成树，然后求这个的直径，割边-直径即是答案

因为有的图上可能有重边，这样不好处理。我们记录每条边的标号（一条无向边拆成的两条有向边标号相同）这样就能限制不走一样的边而能走重边！

// File Name: 1002.cpp

// Author: Zlbing

// Created Time: 2013年08月02日 星期五 18时16分10秒

#pragma comment(linker,"/STACK:102400000,102400000")

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

#include<set>

#include<map>

#include<vector>

#include<cstring>

#include<stack>

#include<cmath>

#include<queue>

using namespace std;

#define CL(x,v); memset(x,v,sizeof(x));

#define INF 0x3f3f3f3f

#define LL long long

#define REP(i,r,n) for(int i=r;i<=n;i++)

#define RREP(i,n,r) for(int i=n;i>=r;i--)

const int MAXN=2e5+;

int n,m;

struct Edge{

    int u,v;

    Edge(){}

    Edge(int a,int b){

        u=a;

        v=b;

    }

};

vector<Edge> edges;

vector<int> G[MAXN];

vector<int> P[MAXN];

int dfs_clock,bcc_cnt;

int pre[MAXN];

int T[MAXN];

//fa为u的父亲边

//这样标识就可以走重边而不能走父亲边

int dfs1(int u,int fa)

{

    int lowu=pre[u]=++dfs_clock;

    for(int i=;i<G[u].size();i++)

    {

        int mm=G[u][i];

        int v=edges[mm].v;

        if(fa==(mm^))continue;

        if(!pre[v])

        {

            int lowv=dfs1(v,mm);

            lowu=min(lowu,lowv);

            if(lowv>pre[u])

            {

                P[v].push_back(u);

                P[u].push_back(v);

            }

        }

        else if(pre[v]<pre[u])

        {

            lowu=min(pre[v],lowu);

        }

    }

    return lowu;

}

void dfs2(int u,int fa)

{

    T[u]=bcc_cnt;

    for(int i=;i<G[u].size();i++)

    {

        int v=edges[G[u][i]].v;

        bool f=true;

        for(int j=;j<P[u].size();j++)

        {

            int vv=P[u][j];

            if(v==vv)

            {

                f=false;break;

            }

        }

        if(!f||T[v])continue;

        dfs2(v,u);

    }

}

void find_bcc(int n)

{

     dfs_clock=,bcc_cnt=;

    memset(pre,,sizeof(pre));

    memset(T,,sizeof(T));

    for(int i=;i<=n;i++)

        if(!pre[i])

            dfs1(i,-);

    for(int i=;i<=n;i++)

        if(!T[i])

        {

            bcc_cnt++;

            dfs2(i,-);

        }

}

vector<int> GG[MAXN];

int d[MAXN];

void dfs(int u,int dep)

{

    d[u]=dep;

    for(int i=;i<GG[u].size();i++)

    {

        int v=GG[u][i];

        if(!d[v])

        {

            dfs(v,dep+);

        }

    }

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        if(n+m==)break;

        REP(i,,n){

            G[i].clear();

            P[i].clear();

        }

        edges.clear();

        int a,b;

        REP(i,,m)

        {

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

            Edge e;

            e=Edge(a,b);

            edges.push_back(e);

            e=Edge(b,a);

            edges.push_back(e);

            int mm=edges.size();

            G[a].push_back(mm-);

            G[b].push_back(mm-);

        }

        find_bcc(n);

        REP(i,,n)

        {

            GG[i].clear();

        }

        /*

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

        {

            printf("T[%d]=%d\n",i,T[i]);

        }

        */

        for(int i=;i<=n;i++)

        {

            for(int j=;j<P[i].size();j++)

            {

                int v=P[i][j];

                if(T[i]!=T[v])

                {

                //    printf("u=%d v=%d\n",T[i],T[v]);

                    GG[T[i]].push_back(T[v]);

                }

            }

        }

        CL(d,);

        dfs(,);

        int maxn=;

        int flag=;

        for(int i=;i<=bcc_cnt;i++)

        {

            if(d[i]>maxn)

            {

                maxn=d[i];

                flag=i;

            }

        }

        CL(d,);

        dfs(flag,);

        maxn=;

        for(int i=;i<=bcc_cnt;i++)

        {

            if(d[i]>maxn)

                maxn=d[i];

        }

    //    printf("bcc_cnt=%d maxn=%d\n",bcc_cnt,maxn);

        cout<<bcc_cnt-maxn<<endl;

    }

    return ;

}