HDU 4612 Warm up

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4612

解题思路：

题的大意是有N个种植园，有M条水渠相连。这就是一个强连通的无向图，他不想要这个图中存在有桥，如果添加一条边，剩余的桥的最小数量。

本题的答案先用Tarjan进行缩点。在这个过程就可以计算出桥的数量。然后怎样添加一条边使的桥的数量最少呢？ 

答案：桥-缩点形成树的直径。

如何求树的直径：

有两种方法

1. 对树进行广度优先搜索，然后以广度优先搜索最后一个访问的点进行优先搜索，然后深度优先搜索形成的这颗树的深度就是树的直径。

2.对树进行深度优先搜索，以深度最深的点，在进行一次深度优先搜索，然后深度优先搜索形成的这颗树的深度就是就是树的直径

注意本题有重边。

实现代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN=200010;
const int MAXM=2000010;

struct Edge{
    int to,next;
    bool cut;  //标记是否是桥
    bool meg;  //标记是否是重边
}edges[MAXM];

int head[MAXN],tot;

void init(){
    memset(head,-1,sizeof(head));
    tot=0;
}

void addEdge(int u,int v,bool meg){
    edges[tot].to=v;
    edges[tot].meg=meg;
    edges[tot].next=head[u];
    edges[tot].cut=false;
    head[u]=tot++;
}

int LOW[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];
bool Instack[MAXN];
int bridge,Index,top;
int block;

void Tarjan(int u,int pre,bool meg){
    DFN[u]=LOW[u]=++Index;
    Stack[top++]=u;
    Instack[u]=true;

    int v;
    for(int i=head[u];i!=-1;i=edges[i].next){
        v=edges[i].to;
        if(v==pre&&(!meg)) continue;

        if(!DFN[v]){
            Tarjan(v,u,edges[i].meg);

            if(LOW[u]>LOW[v]) LOW[u]=LOW[v];

            if(LOW[v]>DFN[u]){
                bridge++;
                edges[i].cut=true;
                edges[i^1].cut=true;
            }
        }else if(Instack[v]&&LOW[u]>DFN[v]) LOW[u]=DFN[v];
    }

    if(DFN[u]==LOW[u]){
        block++;
        do{
            v=Stack[--top];
            Instack[v]=false;
            Belong[v]=block;
        }while(v!=u);
    }
}

vector<int>tree[MAXN];
int dep[MAXN];

//计算树的深度
void dfs(int u){

    for(int i=0;i<tree[u].size();i++){
        int v=tree[u][i];

        if(dep[v]!=-1) continue;
        dep[v]=dep[u]+1;
        dfs(v);
    }
}

void solve(int n){
    memset(DFN,0,sizeof(DFN));
    memset(Instack,0,sizeof(Instack));
    Index=top=bridge=block=0;


    Tarjan(1,0,false);
    for(int i=1;i<=block;i++)
        tree[i].clear();

    for(int i=1;i<=n;i++)
        for(int j=head[i];j!=-1;j=edges[j].next)
            if(edges[j].cut)
                tree[Belong[i]].push_back(Belong[edges[j].to]);

    memset(dep,-1,sizeof(dep));
    int k=1;
    dep[1]=0;
    dfs(1);
    for(int i=1;i<=block;i++){
        if(dep[k]<dep[i])
            k=i;
    }

    memset(dep,-1,sizeof(dep));
    dep[k]=0;
    int ans=0;
    dfs(k);

    for(int i=1;i<=block;i++)
        ans=max(ans,dep[i]);

    printf("%d
",bridge-ans);
}

struct node{
    int u,v;
    bool operator <(const node &rhs) const{
        if(u!=rhs.u)
            return u<rhs.u;
        else
            return v<rhs.v;
    }
};

node nd[MAXM];

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        if(n==0&&m==0) break;
        init();

        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            if(u==v) continue;
            if(u>v) swap(u,v);
            nd[i].u=u;
            nd[i].v=v;
        }
        sort(nd,nd+m);

        for(int i=0;i<m;i++){
            if(i==0||nd[i].u!=nd[i-1].u||nd[i].v!=nd[i-1].v){
                if(i<m-1&&nd[i].u==nd[i+1].u&&nd[i].v==nd[i+1].v){
                    addEdge(nd[i].u,nd[i].v,true);
                    addEdge(nd[i].v,nd[i].u,true);
                }else{
                    addEdge(nd[i].u,nd[i].v,false);
                    addEdge(nd[i].v,nd[i].u,false);
                }
            }
        }
        solve(n);
    }
}