# 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;
}```

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

(0)
(0)

0条