UVA 796 Critical Links
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82833#overview
点的编号 （与这个点相连的点的个数m） 依次是m个点的
桥： 无向连通图中，如果删除某条边后，图变成不连通了，则该边为桥。 在求割点的基础上吗，假如一个边没有重边（重边 1-2, 1->2 有两次，那么 1->2 就是有两条边了，那么 1->2就不算是桥了）。
当且仅当 (u,v) 为父子边，且满足 dfn[u] < low[v]
#include #include #include #include #include #include #include #include #include using namespace std;#define INF 0xfffffff#define N 11005#define min(a,b) (a
G[N];int low[N], dfn[N], f[N], Time, n;void init(){ for(int i = 0; i < n; i++) G[i].clear(); Time = 0; memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(f, 0, sizeof(f));}void Tarjan(int u, int fa){ low[u] = dfn[u] = ++Time; f[u] = fa; int len = G[u].size(), v; for(int i = 0; i < len; i++) { v = G[u][i]; if(!low[v]) { Tarjan(v, u); low[u] = min(low[u], low[v]); } else if(fa != v) low[u] = min(low[u], dfn[v]); }}void slove(){ int ans = 0; for(int i = 0; i < n; i++) //可能不是一个连通图，所以每个点都要遍历 if(!low[i]) Tarjan(i, -1); for(int i = 0; i < n; i++) { int v = f[i]; if(v != -1 && dfn[v] < low[i]) // 是桥的条件 { bridge[ans].x = i; bridge[ans].y = v; if(bridge[ans].x > bridge[ans].y) swap(bridge[ans].x, bridge[ans].y); ans ++; } } sort(bridge, bridge+ans); printf("%d critical links\n", ans); for(int i = 0; i < ans; i++) printf("%d - %d\n", bridge[i].x, bridge[i].y); puts("");}int main(){ int a, b, m; while(scanf("%d", &n) != EOF) { init(); for(int i = 0; i < n; i++) { scanf("%d (%d)", &a, &m); while(m--) { scanf("%d", &b); G[a].push_back(b); G[b].push_back(a); } } slove(); } return 0;}