Network POJ - 3694（lca并查集+连通图求桥）

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <queue>#include <algorithm>#include <vector>#define mem(a, b) memset(a, b, sizeof(a))using namespace std;const int maxn = 400100, INF = 0x7fffffff;int pre[maxn], f[maxn], pa[maxn];int dfs_clock;int n, m, ret;vector<int> G[maxn];int find(int x){ ???return f[x]==x?x:(f[x]=find(f[x]));}int Union(int u, int v){ ???int r = find(u); ???int l = find(v); ???if(r == l) return 0; ???f[r] = l; ???return 1;}int dfs(int u, int fa){ ???pa[u] = fa; ???int lowu = pre[u] = ++dfs_clock; ???for(int i=0; i<G[u].size(); i++) ???{ ???????int v = G[u][i]; ???????if(!pre[v]) ???????{ ????// ??????pa[v] = u; ???????????int lowv = dfs(v, u); ???????????lowu = min(lowu, lowv); ???????????if(lowv > pre[u]) ???????????????ret++; ???????????else ???????????????Union(u, v); ??//如果u和v之间没桥，那么u和v就同属于一个集合 ???????} ???????else if(pre[v] < pre[u] && v != fa) ???????????lowu = min(lowu, pre[v]); ???} ???return lowu;}int lca(int u, int v){ ???int r = find(u); ???int l = find(v); ???if(r == l) ???????return ret; ???if(pre[u] > pre[v]) ???????swap(u, v); ???while(pre[u] < pre[v]) ???{ ???????if(Union(pa[v], v)) ???????????ret--; ???????v = pa[v]; ???} ???while(u != v) ????//v经过上一个while后要么是u 要么是u和v的最近公共祖先 ???{ ???????if(Union(u, pa[u])) ???????????ret--; ???????u = pa[u]; ???} ???return ret;}void init(){ ???mem(pre, 0); ???mem(pa, 0); ???for(int i=0; i<=n; i++) f[i] = i; ???dfs_clock = 0; ???ret = 0;}int main(){ ???int kase = 0; ???while(cin>> n >> m && n+m) ???{ ???????init(); ???????for(int i=0; i<m; i++) ???????{ ???????????int u, v; ???????????cin>> u >> v; ???????????G[u].push_back(v); ???????????G[v].push_back(u); ???????} ???????dfs(1, -1); ???????int Q; ???????cin>> Q; ???????printf("Case %d:\n",++kase); ???????for(int i=0; i<Q; i++) ???????{ ???????????int u, v; ???????????cin>> u >> v; ???????????cout<< lca(u, v) <<endl; ???????} ???} ???return 0;}