https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=737
桥：
一个连通图，无向连通图中，如果删除某条边后，图变成不连通了，则该边为桥；
求桥：
在求割点的基础上吗，假如一个边没有重边（重边 1-2, 1->2 有两次，那么 1->2 就是有两条边了，那么 1->2就不算是桥了）。
当且仅当 (u,v) 为父子边，且满足 dfn[u] < low[v]
#include<iostream> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> #include<stack> #include<queue> #include<vector> using namespace std; #define N 200 int low[N],dfn[N],n,fa[N],Stack[N]; int Time,top,ans[N]; struct node { int x,y; }a[N]; vector<vector <int> >G; void Inn() { G.clear(); G.resize(n+1); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(fa,0,sizeof(fa)); memset(ans,0,sizeof(ans)); memset(Stack,0,sizeof(Stack)); Time=top=0; } bool cmp(node c,node d) { if(c.x!=d.x) return c.x<d.x; else return c.y<d.y; } void Tarjin(int u,int f) { low[u]=dfn[u]=++Time; Stack[top++]=u; fa[u]=f; int len, v; len=G[u].size(); for(int i=0; i<len; i++) { v=G[u][i]; if(!dfn[v]) { Tarjin(v,u); low[u]=min(low[u],low[v]); } else if(f!=v) low[u]=min(low[u],dfn[v]); } } void slove() { int ans=0,i; for(i=0; i<n; i++) { if(!dfn[i]) Tarjin(i,-1); } for(i=0; i<n; i++) { int v=fa[i]; if(v!=-1 && low[i]>dfn[v]) { a[ans].x=i; a[ans].y=v; int t; if(a[ans].x>a[ans].y) { t=a[ans].x; a[ans].x=a[ans].y; a[ans].y=t; } ans++; } } sort(a,a+ans,cmp); printf("%d critical links ",ans); for(i=0; i<ans; i++) printf("%d - %d ",a[i].x,a[i].y); printf(" "); } int main() { int h,m,b,i; while(scanf("%d",&n)!=EOF) { Inn(); for(i=0; i<n; i++) { scanf("%d (%d)",&h,&m); while(m--) { scanf("%d",&b); G[h].push_back(b); G[b].push_back(h); } } slove(); } return 0; } /* 8 0 (1) 1 1 (3) 2 0 3 2 (2) 1 3 3 (3) 1 2 4 4 (1) 3 7 (1) 6 6 (1) 7 5 (0) */