题意
给定一张个点,条边的无向连通图,然后执行次操作,每次向图中添加一条边,并且询问图上桥的数量
前置芝士
无向图的割点和桥
给定无向连通图
1.若对于 ,从图中删去节点以及所有关联边之后,分裂为两个或两个不相连的子图,则称为的割点
2.若对于 ,从图中删去边之后,分裂为两个不相连的子图,则称为的割边或桥割边判定法则
无向边是桥,当且仅当树上存在的一个子节点,满足: 。因为这说明从子节点开始走,不管走那一条边,都无法到达或比更早访问的节点。
如果此时我们把绿边删去,那么图就会断成多个部分,因此他们就是割边。通过找到这些不同的连通块,把他们所成一个点,重新建图
inline void tarjan(int u,int idg) { dfn[u]=low[u]=++cnt; for (int i=h[u];~i;i=las[i]) { int v=to[i]; if(!dfn[v]) { tarjan(v,i); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]) eg[i]=eg[i^1]=1; } else if((idg^1)!=i) low[u]=min(low[u],dfn[v]); //求桥 } }
e-DCC
即边双连通分量(极大边双连通子图),若一张无向连通图不存在桥,则称其为“边双连通图”。求法很简单,因为已经求出了所有的桥,那么我们就找到不通过桥的能够连通的所有子图,把他们划分到一个连通块中。只需要在上面的代码上修改一下
inline void tarjan(int u,int idg) { stk[++tp]=u; dfn[u]=low[u]=++cnt; for (int i=h[u];~i;i=las[i]) { int v=to[i]; if(!dfn[v]) { tarjan(v,i); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]) eg[i]=eg[i^1]=1; } else if((idg^1)!=i) low[u]=min(low[u],dfn[v]); //求桥 } if(low[u]==dfn[u]) { ++tot; int y; do { y=stk[tp--]; id[y]=tot; }while(y!=u); } }
正题
- 先用Tarjan算法求出无向图所有的"边双连通分量",并对每一个"e-DCC"缩点,得到一棵树,那么此时桥的数目就是所点后树的边数
- 一次考虑每一个加边操作,如果属于一个e-DCC,那么缩点后桥的数量不变;若他们属于不同的e-DCC,那么说明他们的缩点后的树上最短路径上的所有边都不再是"桥",于是可以求出他们的LCA,从这些点一步一步跳的父节点并标记沿途的边,这里可以用并查集路径压缩优化。只要此时跳到的深度小于父节点,就不用再跳了。
代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") /* 先求出所有的边双连通分量,缩点 连边,跑dfs,处理这棵无环树,在向上 查找桥时,可以并查集优化 */ #include<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=2e5+10; int tot,cnt,fa,fa2,tp; int h[N],kp[N],id[N],f[20][N],stk[N]; int dfn[N],low[N],eg[N<<1],dep[N],fat[N]; int las[N<<1],to[N<<1]; int now[N<<1],des[N<<1]; queue<int>q; inline void init() { fa=0,fa2=0,cnt=0,tot=0; memset(las,0,sizeof(las)); memset(to,0,sizeof(to)); memset(now,0,sizeof(now)); memset(des,0,sizeof(des)); memset(h,-1,sizeof(h)); memset(kp,-1,sizeof(kp)); memset(dfn,0,sizeof(dfn)); memset(eg,0,sizeof(eg)); } inline void add(int x,int y) { las[fa]=h[x]; to[fa]=y; h[x]=fa++; } inline void adk(int x,int y) { now[fa2]=kp[x]; des[fa2]=y; kp[x]=fa2++; } inline void tarjan(int u,int idg) { stk[++tp]=u; dfn[u]=low[u]=++cnt; for (int i=h[u];~i;i=las[i]) { int v=to[i]; if(!dfn[v]) { tarjan(v,i); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]) eg[i]=eg[i^1]=1; } else if((idg^1)!=i) low[u]=min(low[u],dfn[v]); //求桥 } if(low[u]==dfn[u]) { ++tot; int y; do { y=stk[tp--]; id[y]=tot; }while(y!=u); } } inline void dfs(int u,int v) { dep[u]=dep[v]+1; f[0][u]=v; for (int i=1;i<=18;i++) f[i][u]=f[i-1][f[i-1][u]]; for (int i=kp[u];~i;i=now[i]) { int j=des[i]; if(j==v) continue; dfs(j,u); } } inline int get(int x) { if(x==fat[x]) return x; return fat[x]=get(fat[x]); } inline int Lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for (int i=18;i>=0;i--) if(dep[f[i][x]]>=dep[y]) x=f[i][x]; if(x==y) return x; for (int i=18;i>=0;i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y]; return f[0][x]; } int main() { int T=0;int n,m,u,v; while(scanf("%d%d",&n,&m)&&n) { init(); for (int i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v),add(v,u); } //建边 for (int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0); //找强联通分量 for (int i=1;i<=n;i++) for (int j=h[i];~j;j=las[j]) { v=to[j]; if(id[i]==id[v]) continue; adk(id[i],id[v]); }dfs(1,0); T++;printf("Case %d:\n",T); int q,ans=tot-1;scanf("%d",&q); for (int i=1;i<=tot;i++) fat[i]=i; while(q--) { scanf("%d%d",&u,&v); if(id[u]!=id[v]) { u=id[u],v=id[v]; int lca=Lca(u,v); u=get(u); while(dep[lca]<dep[u]) { fat[u]=f[0][u]; ans--; u=get(u); } v=get(v); while(dep[lca]<dep[v]) { fat[v]=f[0][v]; ans--; v=get(v); } } printf("%d\n",ans); } puts(""); } return 0; }