hdu Caocao's Bridges(无向图边双连通分量，找出权值最小的桥)

/*
    题意：给出一个无向图，去掉一条权值最小边，使这个无向图不再连同！
    
    tm太坑了...
    1,如果这个无向图开始就是一个非连通图，直接输出0
    2，重边（两个节点存在多条边， 权值不一样）
    3，如果找到了桥的最小权值为0，也就是桥上的士兵数为0，那么还是要最少派一个
    士兵过去炸掉桥！ 
    
    思路：假设每两个节点最多只有一条边进行相连！
    进行tarjan算法，如果该算法调用了超过2次，说明这个原图就是不连通的！
    否则在tarjan算法中将桥存起来！然后我们遍历每一座桥，看一看我们找到的
    桥（连接的两个定点分别是u, v）是不是(u, v)只有一条路相连接，如果是的，
    那么就跟新最小值！ 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 1000005
#define INF 0x3f3f3f3f
#define N 1005
using namespace std;
struct EDGE{
   int u, v, w, nt; 
   EDGE(){}
   EDGE(int u, int v, int w, int nt){
       this->u=u;
       this->v=v;
       this->w=w;
       this->nt=nt;         
   }
};

EDGE edge[M];
EDGE brige[M];
int first[N];
int low[N], pre[N];
int dfs_clock;
int n, m, cnt, ret;


void tarjan(int u, int fa){
    low[u]=pre[u]=++dfs_clock;
    for(int e=first[u]; e!=-1; e=edge[e].nt){
         int v=edge[e].v;
        
         if(!pre[v]){
              tarjan(v, u);
              low[u]=min(low[u], low[v]);
              if(low[v]>pre[u])
                 brige[ret++]=edge[e];
         }         
         else if(v!=fa && pre[u]>pre[v])
              low[u]=min(low[u], pre[v]);
    }        
}

int main(){
    while(scanf("%d%d", &n, &m) && (n||m)){
        memset(first, -1, sizeof(first));
        cnt=0;
        while(m--){
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            edge[cnt]=EDGE(u, v, w, first[u]);
            first[u]=cnt++;
            edge[cnt]=EDGE(v, u, w, first[v]);
            first[v]=cnt++;
        }      
        dfs_clock=0;
        ret=0;
        memset(low, 0, sizeof(low));
        memset(pre, 0, sizeof(pre)); 
        int flag=0;
        for(int i=1; i<=n; ++i)
           if(!pre[i]){
              ++flag;
              if(flag==2) break;
              tarjan(i, -1);
           }
        
        int minNum=INF;
        if(flag==2) minNum=0;
        else{
           for(int i=0; i<ret; ++i)
             if(brige[i].w<minNum){//对假定的桥判断 
                int cc=0;
                for(int e=first[brige[i].u]; e!=-1; e=edge[e].nt)
                   if(edge[e].v==brige[i].v) ++cc;
                if(cc==1)  minNum=brige[i].w;//说明是真正的桥 
             }
           if(minNum==INF) minNum=-1;
           else if(minNum==0) minNum=1;//这一句不要忘记了！ 
        }
        printf("%d\n", minNum);
    } 
    return 0;    
}