Network POJ - 3694 （连通图标求桥）

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <stack>#include <algorithm>#include <cmath>#define mem(a, b) memset(a, b, sizeof(a))using namespace std;const int maxn = 10010, INF = 0x7fffffff;int pre[maxn], low[maxn], iscut[maxn];int dfs_clock, n, cnt;vector<int> G[maxn];struct edge{ ???int u, v;}Edge[maxn];int cmp(edge a, edge b){ ???if(a.u == b.u) return a.v < b.v; ???return a.u < b.u;}int dfs(int u, int fa){ ???int lowu = pre[u] = ++dfs_clock; ???int child = 0; ???for(int i=0; i<G[u].size(); i++) ???{ ???????int v = G[u][i]; ???????if(!pre[v]) ???????{ ???????????child++; ???????????int lowv = dfs(v, u); ???????????lowu = min(lowu, lowv); ???????????if(lowv > pre[u]) ???????????{ ???????????????iscut[u] = 1; ???????????????Edge[cnt].u = u, Edge[cnt].v = v; ???????????????if(Edge[cnt].u > Edge[cnt].v) swap(Edge[cnt].u, Edge[cnt].v); ???????????????cnt++; ???????????} ???????} ???????else if(pre[v] < pre[u] && v != fa) ???????????lowu = min(lowu, pre[v]); ???} ???if(fa < 0 && child == 1) iscut[u] = 0; ???low[u] = lowu; ???return lowu;}void init(){ ???cnt = 0; ???dfs_clock = 0; ???mem(pre, 0); ???mem(low, 0); ???mem(iscut, 0); ???for(int i=0; i<=n; i++) G[i].clear();}int main(){ ???while(cin>> n) ???{ ???????init(); ???????for(int i=0; i<n; i++) ???????{ ???????????int u, d, v; ???????????scanf("%d (%d)", &u, &d); ???????????for(int i=0; i<d; i++) ???????????{ ???????????????cin>> v; ???????????????G[u].push_back(v); ???????????????G[v].push_back(u); ???????????} ???????} ???????for(int i=0; i<n; i++) ???????????if(!pre[i]) ???????????????dfs(i, -1); ???????sort(Edge, Edge+cnt, cmp); ???????printf("%d critical links\n",cnt); ???????for(int i=0; i<cnt; i++) ???????????cout<< Edge[i].u << " - " << Edge[i].v <<endl; ???????cout<<endl; ???} ???return 0;}