定义
(在无向图中):在一个连通图中,如果删去其中一条边后,连通块的数量会增多,那么我们称这条边为桥或者是割边.
算法
tarjan，只需要判定low[v]>dfn[u]即可(u为父，v为子)
解释：如果子节点在不走原路情况下到不了父节点或父节点之前的点，那么子节点只能走原路回到父节点及之前节点，原路为必经之路，断掉就会产生新的个联通块，符合割边定义。
例题 HDU-4738
本题细节多多。
首先判断图是否联通，然后判断有无桥，判断桥时注意重边的干扰，最后输出桥的最小边权（如果是0应输出1，至少派一个人去吧）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mid ((st[x].l + st[x].r) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x) {
char c = getchar(),f = 1;x = 0;
for(;c ^ '-' && !isdigit(c);c = getchar());
if(c == '-') c = getchar(),f = -1;
for(;isdigit(c);c = getchar()) x = (x<<1) + (x<<3) + (c ^ '0');
x *= f;
}
template<typename xxx>void print(xxx x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
const int maxn = 2002;
const int inf = 0x7fffffff;
const int mod = 1e9 + 7;
struct edge {
int to,last,val;
// int fg;
}e[2000002];
int head[maxn],tot;
inline void add(int from,int to,int val) {
++tot;
e[tot].to = to;
// e[tot].fg = 0;
e[tot].val = val;
e[tot].last = head[from];
head[from] = tot;
}
int n,m;
int dfn[maxn],low[maxn],cnt;
int mark[2000002],mk;
inline void tarjan(int x,int in_edge) {//通过in_edge到达x
dfn[x] = low[x] = ++cnt;
for(rint i = head[x];i;i = e[i].last) {
if(!dfn[e[i].to]) {
tarjan(e[i].to,i);
if(low[x] > low[e[i].to]) low[x] = low[e[i].to];
if(low[e[i].to] > dfn[x]) {//子节点无法到达我及我之前，则联系我与子节点的边为桥
//这个判断可以防重边对桥的干扰，假设原图有一个桥，tarjan时绝对无法回到父节点及之前节点,
//但是有重边时 子节点通过重边“回到父节点”更新low[e[i].to] == dfn[x],结果无法被判为桥
// e[i].fg = e[i^1].fg = 1;//可这样记录重边
mark[++mk] = e[i].val;
}
}
else if(i ^ (in_edge ^ 1) && dfn[e[i].to] < low[x]) low[x] = dfn[e[i].to];//保证无重边时不会被父亲更新
}
}
int main()
{
while(1) {
tot = 1;
mk = 0;
cnt = 0;
read(n);read(m);
if(!n && !m) break;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,0,sizeof(head));
for(rint i = 1;i <= m; ++i) {
int a,b,c;
read(a);read(b);read(c);
add(a,b,c);add(b,a,c);
}
int k = 0;
for(rint i = 1;i <= n; ++i) {
if(!dfn[i]) {
tarjan(i,0);
++k;
}
}
if(mk == 0) {//无桥，
printf("-1
");
} else {
stable_sort(mark + 1,mark + mk + 1);
if(k > 1) printf("0
");
else if(mark[1])printf("%d
",mark[1]);
else printf("1
");//没人守也要派一个人去占领
}
}
return 0;
}
/*
6 8
1 2 1
2 1 2
1 3 3
3 4 4
4 1 5
2 5 6
2 6 7
5 6 8
6 7
1 2 1
1 3 3
3 4 4
4 1 5
2 5 6
2 6 7
5 6 8
*/