Content #
无向边x-y是桥，当且仅当在搜索树上存在x的一个子节点y时，满足
low[y]>dfn[x]
也就是说，若孩子的low值比自己的dfn值大，则从该节点到这个孩子的边为桥。
void find_bridge(int u, int father) {
dfn[u] = low[u] = num++;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == father) continue;
if (! dfn[v]) {
find_bridge(v, u);
low[u] = min(low[v], low[u]);
if (low[v] > dfn[u]) {
cout << "u - v is bridge" <<endl;
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
From #
《算法训练营入门篇》 陈小玉