http://poj.org/problem?id=3694
用tarjan算出桥，用lca算出公共祖先 把路上的边更新掉 原来的桥变为不是桥 看一解题报告感觉有一部分是不用加的 不知道是不是数据水 没加交上也A了。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define N 1000010
#define M 2000010
struct node
{
int u,v,next;
}edge[M*];
int head[N],t,dfn[N],iscut[N],fa[N],low[N],num,dc;
void init()
{
t = ;
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
fa[] = ;
num=;
dc=;
}
void add(int u,int v)
{
edge[t].u = u;
edge[t].v = v;
edge[t].next = head[u];
head[u] = t++;
edge[t].u = v;
edge[t].v = u;
edge[t].next = head[v];
head[v] = t++;
}
void tarjan(int u,int faa)
{
int i,flag=;
dfn[u] = low[u] = ++dc;
for(i = head[u] ; i != - ; i = edge[i].next)
{
int v = edge[i].v;
if(flag&&faa==v)
{
flag = ;
continue;
}
if(!dfn[v])
{
fa[v] = u;
tarjan(v,u);
low[u] = min(low[v],low[u]);
if(low[v]>dfn[u])
{
num++;
iscut[v] = ;
}
}
else
low[u] = min(dfn[v],low[u]);
}
}
void lca(int u,int v)
{
int t;
if(dfn[u]<dfn[v])
{t = u;u = v;v = t;}
while(dfn[u]>dfn[v])
{
if(iscut[u])
{
iscut[u] = ;
num--;
}
u = fa[u];
}
while(u!=v)
{
if(iscut[v])
{
iscut[v] = ;
num--;
}
/*if(iscut[u])
{
iscut[u] = 0;
num--;
}*/
v = fa[v];u = fa[u];
}
}
int main()
{
int n,m,q,a,b,kk=;
while(cin>>n>>m)
{
kk++;
if(n==&&m==)
break;
init();
while(m--)
{
cin>>a>>b;
add(a,b);
}
tarjan(,);
printf("Case %d:\n",kk);
cin>>q;
while(q--)
{
cin>>a>>b;
lca(a,b);
cout<<num<<endl;
}
puts("");
}
return ;
}