HDU 4738 Caocao's Bridges ——（找桥，求联通块）

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <queue>
  5 #include <stack>
  6 #include <vector>
  7 using namespace std;
  8 typedef long long ll;
  9 const int N = 1000 + 5;
 10 
 11 int n,m,head[N],tot,scc_cnt,dfn[N],low[N],dfs_clock,cnt;
 12 bool vis[N*N],use[N];
 13 //stack<int> S;
 14 struct edge
 15 {
 16     int v,nxt,w;
 17 }edges[N*N];
 18 struct bridge
 19 {
 20     int u,v,w;
 21     bool operator < (const bridge &temp) const
 22     {
 23         return w<temp.w;
 24     }
 25 };
 26 vector<bridge> bridges;
 27 void addEdge(int u,int v,int w)
 28 {
 29     edges[tot] = (edge){v,head[u],w};
 30     head[u] = tot++;
 31     edges[tot] = (edge){u,head[v],w};
 32     head[v] = tot++;
 33 }
 34 
 35 void init()
 36 {
 37     memset(head,-1,sizeof(head));
 38     tot = 0;
 39     //scc_cnt = 0;
 40     dfs_clock = 0;
 41     memset(dfn,0,sizeof(dfn));
 42     bridges.clear();
 43     memset(vis,false,sizeof(vis));
 44     cnt = 0;
 45     memset(use,false,sizeof(use));
 46 }
 47 
 48 void tarjan(int u)
 49 {
 50     dfn[u] = low[u] = ++dfs_clock;
 51     //S.push(u);
 52     for(int i=head[u];i!=-1;i=edges[i].nxt)
 53     {
 54         if(vis[i]) continue;
 55         // 因为可能存在有重边，所以这里必须这么写
 56         vis[i] = vis[i^1] = true;
 57         int v = edges[i].v;
 58         if(!dfn[v])
 59         {
 60             tarjan(v);
 61             low[u] = min(low[u],low[v]);
 62             if(low[v] > dfn[u]) bridges.push_back((bridge){u,v,edges[i].w});
 63         }
 64         else if(dfn[v] < dfn[u])
 65         {
 66             low[u] = min(low[u],dfn[v]);
 67         }
 68     }
 69     /*if(dfn[u]==low[u])
 70     {
 71         scc_cnt++;
 72         for(;;)
 73         {
 74             int x = S.top();S.pop();
 75             if(x == u) break;
 76         }
 77     }*/
 78 }
 79 
 80 void dfs(int u)
 81 {
 82     use[u] = true;
 83     for(int i=head[u];i!=-1;i=edges[i].nxt)
 84     {
 85         int v = edges[i].v;
 86         if(use[v]) continue;
 87         dfs(v);
 88     }
 89 }
 90 
 91 void solve()
 92 {
 93     for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
 94     for(int i=1;i<=n;i++)
 95     {
 96         if(!use[i])
 97         {
 98             cnt++;
 99             dfs(i);
100         }
101     }
102 
103     if(cnt==1)
104     {
105         if(bridges.size()==0) puts("-1");
106         else
107         {
108             sort(bridges.begin(),bridges.end());
109             printf("%d\n",bridges[0].w==0?1:bridges[0].w);
110             // 如果这座桥上没有人，周瑜也必须派一个人去放置炸弹
111         }
112     }
113     else puts("0");
114 }
115 
116 int main()
117 {
118     while(scanf("%d%d",&n,&m)==2)
119     {
120         if(n==0 && m==0) break;
121         init();
122         for(int i=1;i<=m;i++)
123         {
124             int u,v,w;scanf("%d%d%d",&u,&v,&w);
125             addEdge(u,v,w);
126         }
127         solve();
128     }
129 }