就是求出原先图中的桥的数量，在每一次询问时加入一条新边，求加入当前边后图中剩余的桥的数量
求出原先图中的桥的数量，然后减去新加入边的两端点之间的桥的数量，就是剩余桥的数量。。
用并查集把属于同一集合的放到一起（即两个点之间没有桥的）
#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 = , 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 ;
f[r] = l;
return ;
} int dfs(int u, int fa)
{
pa[u] = fa;
int lowu = pre[u] = ++dfs_clock;
for(int i=; 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, );
mem(pa, );
for(int i=; i<=n; i++) f[i] = i;
dfs_clock = ;
ret = ;
} int main()
{
int kase = ;
while(cin>> n >> m && n+m)
{
init();
for(int i=; i<m; i++)
{
int u, v;
cin>> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(, -);
int Q;
cin>> Q;
printf("Case %d:\n",++kase);
for(int i=; i<Q; i++)
{
int u, v;
cin>> u >> v;
cout<< lca(u, v) <<endl;
} } return ;
}