用tarjan求桥上的最小权值
#include<bits/stdc++.h> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const int N=1e6+7; const ll mod=1e9+7; struct edge{ int v,next,w; }; edge e[N<<1]; int head[N],cnt = 1,dfn[N],low[N],num = 0,bridge[N]; void init(){ memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(bridge,0,sizeof(bridge)); cnt=1; num=0; } void add(int u,int v,int w){ e[++cnt].next=head[u]; e[cnt].v=v; e[cnt].w=w; head[u]=cnt; } void tarjan(int u,int edge){ dfn[u]=low[u]=++num; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; int w=e[i].w; if(!dfn[v]){ tarjan(v,i); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) bridge[i]=bridge[i^1]=1; }else if(i!=(edge^1)) low[u]=min(low[u],low[v]); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; while(cin>>n>>m){ if(n==0&&m==0) break; init(); for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } tarjan(1,-1); bool f=0; for(int i=1;i<=n;i++) if(!dfn[i]) f=1; if(f){ cout<<"0 "; continue; } int ans=inf; for(int i=2;i<=cnt;i++){ if(bridge[i]) ans=min(ans,e[i].w); } if(ans==inf) cout<<"-1 "; else{ if(ans==0) cout<<"1 "; else cout<<ans<<" "; } } return 0; }