定义
在无向图中):在一个连通图中,如果删去其中一条边后,连通块的数量会增多,那么我们称这条边为桥或者是割边.
算法
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 readxxx &x) {
char c = getchar),f = 1;x = 0;
for;c ^ '-' && !isdigitc);c = getchar));
ifc == '-') c = getchar),f = -1;
for;isdigitc);c = getchar)) x = x<<1) + x<<3) + c ^ '0');
x *= f;
}
template<typename xxx>void printxxx x)
{
ifx<0){putchar'-');x=-x;}
ifx>9) printx/10);
putcharx%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 addint 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 tarjanint x,int in_edge) {//通过in_edge到达x
dfn[x] = low[x] = ++cnt;
forrint i = head[x];i;i = e[i].last) {
if!dfn[e[i].to]) {
tarjane[i].to,i);
iflow[x] > low[e[i].to]) low[x] = low[e[i].to];
iflow[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 ifi ^ in_edge ^ 1) && dfn[e[i].to] < low[x]) low[x] = dfn[e[i].to];//保证无重边时不会被父亲更新
}
}
int main)
{
while1) {
tot = 1;
mk = 0;
cnt = 0;
readn);readm);
if!n && !m) break;
memsetdfn,0,sizeofdfn));
memsetlow,0,sizeoflow));
memsethead,0,sizeofhead));
forrint i = 1;i <= m; ++i) {
int a,b,c;
reada);readb);readc);
adda,b,c);addb,a,c);
}
int k = 0;
forrint i = 1;i <= n; ++i) {
if!dfn[i]) {
tarjani,0);
++k;
}
}
ifmk == 0) {//无桥，
printf"-1
");
} else {
stable_sortmark + 1,mark + mk + 1);
ifk > 1) printf"0
");
else ifmark[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
*/