题意：给你一个连通图，然后再给你n个询问，每个询问给一个点u,v表示加上u,v之后又多少个桥。一个最容易想到的办法就是先加边找桥，加边找桥，这样可定超时。那么就可以缩点，因为如果一条边不是桥那么无论怎么加边他肯定都不会变成桥，这样我吧不是桥的点缩成一个点。这样全图就都是桥，这样的话，我们就在加的遍里面去找如果加的边是同一个点，那么，肯定不会减少桥，但是如果不是同一个，那么桥肯定减少~。
代码如下：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#define loop(s,i,n) for(i = s;i < n;i++)
#define cl(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = ;
int low[maxn],dfn[maxn],set[maxn],father[maxn],dfsclock,cut;
vector<int >g[maxn];
int find(int x)
{
if(set[x] != x)
set[x] = find(set[x]); return set[x];
}
int merge(int x,int y)
{
x = find(x);
y = find(y);
if(y != x)
{
set[y] = x;
return ;
}
return ;
} void tarjan(int u,int pre)
{
int v,i,j;
dfn[u] = low[u] = ++dfsclock;
loop(,i,g[u].size())
{
v = g[u][i];
if(!dfn[v])
{
tarjan(v,u);
father[v] = u;
low[u] = min(low[v],low[u]);
if(low[v] > dfn[u])
cut++;
else
merge(u,v);
}
else if(v != pre)
low[u] = min(low[u],dfn[v]);
}
}
void lca(int u,int v)
{ while(u != v)
{
while(dfn[u] >= dfn[v] && u != v)
{
if(merge(u,father[u]))
cut--;
u = father[u];
}
while(dfn[v] >= dfn[u] && u != v)
{
if(merge(v,father[v]))
cut--;
v = father[v];
}
}
}
int main()
{
int n,m;
int i,x,y,cas = ;
while(scanf("%d %d", &n,&m)&&(n||m))
{
int u,v;
printf("Case %d:\n",++cas);
loop(,i,n+)
{
g[i].clear();
set[i] = i;
father[i] = ;
}
while(m--)
{
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u); }
cl(dfn,);
cl(low,);
cut = dfsclock = ; int k;
scanf("%d",&k);
tarjan(,-); while(k--)
{
scanf("%d %d",&u,&v);
lca(u,v);
printf("%d\n",cut);
}
puts("");
}
return ;
}