<题目链接>
题目大意：
给一个无向图，该图只有一个连通分量。然后查询q次，q < 1000, 求每次查询就增加一条边，求剩余桥的个数。
解题分析：
普通的做法就是在每加一条边后，都找一次桥，但是这样肯定超时。
第一种做法是：缩点，因为如果一条边不是桥那么无论怎么加边他肯定都不会变成桥，这样把连通分量缩成一个点。这样全图所有的边就都是桥，这样的话，我们就在加的边里面去找如果加的边是同一个点，那么，肯定不会减少桥，但是如果不是同一个，那么桥肯定减少。
还有一种做法：因为需要u、v之间直接连一条边，所以u->v的原始路径与新连的这条边构成一个环，所以u->v原始路径上的所有桥将不复存在。我们可以先利用Tarjan处理出原图中所有的桥，然后再利用LCA将u->v原始路径的每一条边都求出来(求出u到LCA的所有边和v到LCA的所有边)，然后判断该边是否是桥即可，如果是桥，则删除该边的桥标记即可。
下面介绍第二种做法：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; #define clr(a,b) memset(a,b,sizeof(a))
const int N = 1e5+;
const int M = 4e5+;
int n,m,q,tot,index,bridge;
int dfn[N],low[N],fa[N],dep[N],head[N];
bool cut[N];
struct Edge{
int to,next;
}edge[M];
void init(){
tot=bridge=index=;
clr(head,-);clr(dfn,);clr(dep,);clr(cut,false);
}
void addedge(int u,int v){
edge[tot].to=v,edge[tot].next=head[u];
head[u]=tot++;
}
void tarjan(int u,int pre){
dfn[u]=low[u]=++index;
dep[u]=dep[pre]+; //dep代表该点深度
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].to;
if(v==pre) continue;
if(!dfn[v]){
fa[v]=u;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){ //桥的判定定理
cut[v]=; //标记v所在边为桥
bridge++;
}
}
else
low[u]=min(low[u],dfn[v]);
}
}
void LCA(int u,int v){ //利用LCA将u->v原始路径上的所有桥全部删除
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]>dep[v]){ //将u跳到与v深度相同,将路径上碰到的桥全部删除
if(cut[u]){
bridge--;
cut[u]=false;
}
u=fa[u];
}
while(u!=v){ //将u和v同时跳到他们的LCA,在路径中，凡是碰到桥，将该桥删除
if(cut[u]){
bridge--;
cut[u]=false;
}
if(cut[v]){
bridge--;
cut[v]=false;
}
u=fa[u],v=fa[v];
}
}
int main(){
int ncase=;
while(~scanf("%d%d",&n,&m) && (n||m)){
init();
for(int i=; i<=m; i++){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
tarjan(,); //预处理出原图中所有的桥
scanf("%d",&q);
printf("Case %d:\n",++ncase);
while(q--){
int u,v;scanf("%d%d",&u,&v);
LCA(u,v); //u,v之间连一条边，则改变与u->v的原始路径构成环，所以u->v原始路径上的所有桥将不复存在
printf("%d\n",bridge);
}puts("");
}
return ;
}
2018-11-06