题意:给定一张(n)个点(m)条边的无向图,有(Q)组询问,每组询问向图中添加一条边,并且询问当前无向图中"桥"的数量.(n<=1e5,m<=2*1e5,Q<=1000).
分析:无向图(tarjan)求出图中的(e-DCC),然后缩点之后就是一棵树,对于一棵树每次加一条边,就查询这条边的两个端点之间的路径上的边数即可.
可以直接找到两个点的lca,然后暴力向上跳,并统计边数:(数据水,可以过)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1e5+5;
const int M=4e5+5;
int n,m,f[N][25],dep[N],bj[N];
int tot,head[N],nxt[M],to[M];
int totc,headc[N],nxtc[M],toc[M];
int tim,dcc,dfn[N],low[N],bridge[M],belong[N];
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void addc(int a,int b){
nxtc[++totc]=headc[a];headc[a]=totc;toc[totc]=b;
}
inline void tarjan(int x,int in_edge){//无向图tarjan找桥
dfn[x]=low[x]=++tim;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y])bridge[i]=bridge[i^1]=1;
}
else if(i!=(in_edge^1))low[x]=min(low[x],dfn[y]);
}
}
inline void dfs(int x){//找到桥后的缩点
belong[x]=dcc;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(belong[y]||bridge[i])continue;
dfs(y);
}
}
inline void Dfs(int u,int fa){//LCA预处理
for(int j=1;j<=20;++j)
f[u][j]=f[f[u][j-1]][j-1];
for(int i=headc[u];i;i=nxtc[i]){
int v=toc[i];if(v==fa)continue;
f[v][0]=u;dep[v]=dep[u]+1;Dfs(v,u);
}
}
inline int LCA(int x,int y){//LCA查询
if(dep[x]<dep[y])swap(x,y);
for(int j=20;j>=0;--j)
if(dep[f[x][j]]>=dep[y])x=f[x][j];
if(x==y)return x;
for(int j=20;j>=0;--j)
if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];
return f[x][0];
}
int main(){
int T=0;
while(1){
n=read();m=read();++T;if(!n&&!m)break;
tot=1;tim=0;dcc=0;memset(head,0,sizeof(head));
totc=1;memset(headc,0,sizeof(headc));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(belong,0,sizeof(belong));
memset(bridge,0,sizeof(bridge));
memset(dep,0,sizeof(dep));
memset(bj,0,sizeof(bj));//多组数据初始化
for(int i=1;i<=m;++i){
int a=read(),b=read();
add(a,b);add(b,a);
}
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i,0);
for(int i=1;i<=n;++i)if(!belong[i])++dcc,dfs(i);
for(int i=2;i<=tot;++i){
int x=to[i^1],y=to[i];
if(belong[x]==belong[y])continue;
addc(belong[x],belong[y]);
}//重新建图
Dfs(1,0);
int Q=read(),ans=totc/2;//初始答案,就是树上的边数(=点数-1)
printf("Case %d:
",T);
while(Q--){
int x=read(),y=read();
x=belong[x];y=belong[y];
if(x==y){
printf("%d
",ans);
continue;
}
int lca=LCA(x,y);
if(!lca)lca=1;
while(x!=lca){
if(!bj[x])bj[x]=1,--ans;
x=f[x][0];
}
while(y!=lca){
if(!bj[y])bj[y]=1,--ans;
y=f[y][0];
}
printf("%d
",ans);
}
printf("
");
}
return 0;
}
也可以用并查集来维护一下,优化时间复杂度.
for(int i=1;i<=dcc;++i)fa[i]=i;
while(Q--){
int x=read(),y=read();
x=belong[x];y=belong[y];
if(x==y){
printf("%d
",ans);
continue;
}
int lca=LCA(x, y);
x=get(x);
while(dep[x]>dep[lca]){
fa[x]=f[x][0];
--ans;
x=get(x);
}
y=get(y);
while(dep[y]>dep[lca]){
fa[y]=f[y][0];
--ans;
y=get(y);
}
printf("%d
", ans);
}