链接:http://poj.org/problem?id=3694
题意:给定一个有向连通图，每次增加一条边，求剩下的桥的数量。
思路：
给定一个无向连通图，添加一条u->v的边，求此边对图剩余的桥的数量的影响:
若u,v在同一个边双联通分量中，则是否添加无影响。否则从u,v的LCA到u,v的边上所有的桥都不再是桥。
在Tarjan算法中，对在同一个边双联通分量中的点使用并查集合并，实现缩点，同时记录父亲节点。若u,v属于不同的边双连通分量，将dfn较大的点(设为v)向上合并直到dfn[v] < dfn[u]，再将u向上合并直到u = v。合并过程中，若发现桥则剩余桥的数量减1。
合并采用并查集，要在合并过程中对路径进行优化，否则超时。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<algorithm>
const int INF = 0x3F3F3F3F;
using namespace std;
typedef long long LL; const int N=,M=;
int head[N],tot,n,m,dfn[N],deep;
int bridge;
int fa[N], cnt[N], pre[N];
struct Node{
int to,next;
}e[M];
void init(){
memset(head, -, sizeof(head));
tot = ;
bridge = ;
for(int i = ; i <= n; i++){
fa[i] = i;
cnt[i] = ;
}
} int Find(int x){
while(x != fa[x]){
x = fa[x];
}
return x;
}
bool Union(int x, int y){
int fx = Find(x);
int fy = Find(y);
if(fx!=fy){
if(cnt[fx]>cnt[fy]){
fa[fy]=fx;
cnt[fx]+=cnt[fy];
}else{
fa[fx]=fy;
cnt[fy]+=cnt[fx];
}
return true;
}else{
return false;
}
}
inline void add(int u, int to){
e[tot].to=to;
e[tot].next=head[u];
head[u]=tot++;
}
int dfs(int u, int fa){
int lowu = dfn[u] = ++deep;//lowu为u及其后代所能到达的最远祖先
for(int i=head[u];~i;i=e[i].next){
int v = e[i].to;
if(!dfn[v]){//树叶边，u到v且v未被访问
pre[v] = u;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if(lowv > dfn[u]){
bridge++;
}else{
Union(u, v);
}
}else if(dfn[v] < dfn[u] && v != fa){
lowu = min(lowu, dfn[v]);//后向边
}
}
return lowu;
} void tarjan(){
memset(dfn, , sizeof(dfn));
deep=;
for(int i=;i<=n;i++){
if(!dfn[i]){
pre[i] = i;
dfs(i,-);
}
}
} int LCA(int u, int v){
if(Find(u) == Find(v)){
return bridge;
}
if(dfn[u] > dfn[v]){
swap(u, v);
}
while(dfn[u] < dfn[v]){
if(Union(v, pre[v])){
bridge--;
}
v = pre[v];
}
while(u != v){
if(Union(u, pre[u])){
bridge--;
}
u = pre[u];
}
return bridge;
} int main(){
int t = ;
while(~scanf("%d %d", &n, &m) && (n || m)){
init();
int a, b, q;
while(m--){
scanf("%d %d", &a, &b);
add(a, b);
add(b, a);
}
tarjan();
scanf("%d", &q);
printf("Case %d:\n",++t);
while(q--){
scanf("%d %d", &a, &b);
printf("%d\n", LCA(a, b));
}
printf("\n");
}
return ;
}