题目描述
给定一张 N 个点 M 条边的无向连通图,然后执行 Q 次操作,每次向图中添加一条边,并且询问当前无向图中“桥”的数量。
算法1
图与缩点图公用数据结构
无需LCA
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=400010;
int ver[M],nxt[M],head[N*2],tot; //缩点图存在N+之后
int timer,dfn[N],low[N],bridge[M];
int c[N],d[N*2],fa[N*2],go[N*2];
int n,m,q,dcc,ans,T;
void add(int x,int y){
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void tarjan(int x,int in){//in:in edge
dfn[x]=low[x]=++timer;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y])
bridge[i]=bridge[i^1]=true;
} else if(i!=(in^1))
low[x]=min(low[x],dfn[y]);
}
}
void dfs(int x){
c[x]=dcc;
for(int i=head[x];i;i=nxt[i])
if(!c[ver[i]] && !bridge[i]) dfs(ver[i]);
}
void dfs_c(int x){
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(d[y])continue;
d[y]=d[x]+1;
go[y]=x;
dfs_c(y);
}
}
int get(int x){
return x==fa[x]?x:(fa[x]=get(fa[x]));
}
void calc(int x,int y){ //不需要LCA,可以走到LCA前面靠根的位置
x=get(x),y=get(y); //并查集就可以,走过LCA对性能几乎没影响
while(x!=y){ //因为有路径压缩
if(d[x]<d[y])swap(x,y);
if(x==N+1)break;
fa[x]=get(go[x]);
ans--;
x=get(x);
}
}
int main(){
while(cin>>n>>m,n){
tot=1;
memset(head, 0, sizeof head);
memset(dfn,0,sizeof dfn);
memset(c,0,sizeof c);
memset(d,0,sizeof d);
memset(bridge,0,sizeof bridge);
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
tarjan(1,0); //找桥
dcc=0;
for(int i=1;i<=n;i++){ //强连通分支
if(c[i])continue;
dcc++;
dfs(i);
}
int oldtot=tot;
for(int i=2;i<=oldtot;i++){//建缩点图
int x=ver[i],y=ver[i^1];
if(c[x]==c[y])continue;
add(N+c[x],N+c[y]), add(N+c[y],N+c[x]);
}
ans=dcc-1;
d[N+1]=1; //N+1为缩点图的根
dfs_c(N+1);//递归求深度和父节点
for(int i=1;i<=dcc;i++)fa[N+i]=N+i;
printf("Case %d:\n",++T);
cin>>q;
for(int i=1;i<=q;i++){
int x,y;
scanf("%d%d",&x,&y);
x=N+c[x],y=N+c[y];
if(x!=y)calc(x,y);
printf("%d\n",ans);
}
puts("");
}
}