/*
给定一个无向图，往里面加边，问加第i条边时图中的桥数
首先肯定要求初始状态下的桥，染色缩点
每次给定的边为(u,v), 那么u->lca(u,v)->v路上的所有边都不再是桥 求LCA时可以直接暴力，一个一个点往上找即可，网上好多题解都是用并查集做的。。
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
struct Edge{
int to,nxt,cut;}edge[maxn<<
1],edge_c[maxn<<
1];
int head[maxn],tot,head_c[maxn],tot_c,n,m,q;
void addedge(
int u,
int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++
;
edge[tot].cut=
0;
}
void add_c(
int u,
int v){
edge_c[tot_c].to=
v;
edge_c[tot_c].nxt=
head_c[u];
head_c[u]=tot_c++
;
}
int dfn[maxn],low[maxn],ind,c[maxn],dcc;
void tarjan(
int u,
int in_edge){
dfn[u]=low[u]=++
ind;
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
if(!
dfn[v]){
tarjan(v,i);
low[u]=
min(low[u],low[v]);
if(dfn[u]<
low[v])
edge[i].cut=edge[i^
1].cut=
1;
}
else if(i!=(in_edge^
1))
low[u]=
min(low[u],dfn[v]);
}
}
void dfs1(
int u){
c[u]=
dcc;
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
if(c[v]||edge[i].cut)
continue;
dfs1(v);
}
}
int dep[maxn],fa[maxn],flag[maxn];
//flag[u]表示u上点的边使割边
void dfs2(
int u,
int pre,
int deep){
dep[u]=deep;fa[u]=pre;flag[u]=
1;
for(
int i=head_c[u];i!=-
1;i=
edge_c[i].nxt){
int v=
edge_c[i].to;
if(v==pre)
continue;
dfs2(v,u,deep+
1);
}
}
int lca(
int u,
int v){
int res=
0;
if(dep[u]<
dep[v])swap(u,v);
while(dep[u]>
dep[v]){
if(flag[u])
res++,flag[u]=
0;
u=
fa[u];
}
while(u!=
v){
if(flag[u])
res++,flag[u]=
0;
if(flag[v])
res++,flag[v]=
0;
u=
fa[u];
v=
fa[v];
}
return res;
}
void init(){
memset(head,-
1,
sizeof head);
memset(head_c,-
1,
sizeof head_c);
memset(dep,0,
sizeof dep);
memset(fa,0,
sizeof fa);
memset(flag,0,
sizeof flag);
memset(c,0,
sizeof c);
memset(dfn,0,
sizeof dfn);
memset(low,0,
sizeof low);
tot=tot_c=ind=dcc=
0;
}
int main(){
int tt=
0;
while(cin>>n>>
m,n){
init();
for(
int i=
1;i<=m;i++
){
int u,v;
cin>>u>>
v;
addedge(u,v);
addedge(v,u);
}
tarjan(1,
0);
dcc=
0;
//染色
for(
int i=
1;i<=n;i++
)
if(!
c[i]){
++
dcc;
dfs1(i);
}
int ans=
0;
for(
int i=
0;i<tot;i++){
//缩点
int v=edge[i].to,u=edge[i^
1].to;
if(c[u]==c[v])
continue;
add_c(c[u],c[v]);
if(edge[i].cut)ans++
;
}
ans/=
2;
printf("Case %d:\n",++
tt);
dfs2(1,
0,
1);
//求出dep数组
cin>>
q;
for(
int i=
1;i<=q;i++
){
int u,v;
cin>>u>>
v;
ans-=
lca(c[u],c[v]);
printf("%d\n",ans);
}
/* for(int i=1;i<=n;i++)
cout<<i<<" "<<c[i]<<" "<<dep[c[i]]<<" "<<fa[c[i]]<<endl;
*/
puts("");
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10458351.html
