题意： 给出一个无向连通图，q次增加后询问，问每次增加后剩余“桥（割边）”的数量。
思路：
先将所有的边双连通分量找到，缩点变成树，找到dcc个数，桥数即为dcc-1；
对于每个询问，若c[x]==c[y]无影响；反之，在树上找到c[x]、c[y]的LCA，再将路上的桥变为0，sum++，最后桥数减去sum。；
代码：
#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;const int N=1e5+10;const int M=2*1e5+10;struct node{ ???int nxt,to;}bian[2*M];int head[N];int cnt1=1;int pre[N],nxt[2*M],to[2*M];int cnt2=1;int dfn[N],low[N];int ???tot,c[N];bool bri[2*M];int fa[N];int num;int dcc;int n,m;int f[N][30];int dep[N];int root;int L;bool exi[2*N+10];void add(int x,int y){ ???bian[++cnt1].nxt=head[x]; ???bian[cnt1].to=y; ???head[x]=cnt1;}void add_c(int x,int y){ ???nxt[++cnt2]=pre[x]; ???to[cnt2]=y; ???pre[x]=cnt2;}void tarjan(int x,int in){ ???dfn[x]=low[x]=++num; ???for(int i=head[x];i;i=bian[i].nxt) ???{ ???????int y=bian[i].to; ???????if(!dfn[y]) ???????{ ???????????tarjan(y,i); ???????????low[x]=min(low[x],low[y]); ???????????if(low[y]>dfn[x]) ???????????{ ???????????????bri[i]=bri[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=bian[i].nxt) ???{ ???????int y=bian[i].to; ???????if(c[y]||bri[i]) continue; ???????dfs(y); ???}}void build(){ ???for(int i=2;i<=cnt1;i++) ???{ ???????int x=bian[i].to; ???????int y=bian[i^1].to; ???????if(c[x]==c[y]) continue; ???????add_c(c[x],c[y]); ??????}}void zbb(int x,int d,int fc){ ???dep[x]=d; ???for(int i=pre[x];i;i=nxt[i]) ???{ ???????int y=to[i]; ???????if(y!=fc) ???????{ ???????????f[y][0]=x; ???????????fa[y]=i; ???????????exi[i]=1; ???????????zbb(y,d+1,x); ???????} ??????}}void father(){ ???dep[0]=-1; ???dep[1]=0; ???for(int i=pre[1];i;i=nxt[i]) ???{ ???int y=to[i]; ???f[y][0]=1; ???fa[y]=i; ???exi[i]=1; ???zbb(y,1,1); ???} ???for(int i=1;i<=30;i++) ???{ ???????if((2<<i)>n) ???????{ ???????????L=i-1;break; ???????????} ???} ???for(int j=1;j<=L;j++) ???for(int i=1;i<=n;i++) ???{ ???????f[i][j]=f[f[i][j-1]][j-1]; ???} ??}int lca(int x,int y){ ???if(dep[x]<dep[y]) swap(x,y); ???for(int j=L;j>=0;j--) ???{ ???????if(dep[f[x][j]]>=dep[y]) ??????????x=f[x][j]; ???} ???if(x==y) return x; ???for(int j=L;j>=0;j--) ???{ ???????if(f[x][j]!=f[y][j]) ???????x=f[x][j],y=f[y][j]; ???} ???return f[x][0];}void work(int x,int end){ ???if(x==end) return; ???int bb=-5; ???int sum=0; ???while(bb!=end) ???{ ???????bb=f[x][0]; ???????if(exi[fa[x]]) ???????{ ???????????exi[fa[x]]=0; ???????????sum++; ?????????} ???????x=bb; ???} ???dcc-=sum;}void clear(){ ???memset(to,0,sizeof to); ???memset(pre,0,sizeof pre); ???memset(nxt,0,sizeof nxt); ???memset(bri,0,sizeof bri); ???memset(bian,0,sizeof (struct node)*2*M); ???memset(head,0,sizeof head); ???cnt1=1;cnt2=1; ???num=0;tot=0;dcc=0; ???root=1;L=0; ???memset(dfn,0,sizeof dfn); ???memset(low,0,sizeof low); ???memset(fa,0,sizeof fa); ???memset(f,0,sizeof f); ???memset(dep,0,sizeof dep); ???memset(c,0,sizeof c); ???memset(exi,0,sizeof exi);}int main(){ ???int shu=0; ???while(1) ???{ ???????scanf("%d%d",&n,&m); ???????if(n==0&&m==0) break; ???????shu++; ???????clear(); ???????int x,y; ???????for(int i=1;i<=m;i++) ???????{ ???????????scanf("%d%d",&x,&y); ???????????add(x,y);add(y,x); ??????????} ???????tarjan(1,0); ???????for(int i=1;i<=n;i++) ???????{ ???????????if(!c[i]) ???????????{ ???????????????dcc++; ???????????????dfs(i); ??????????????} ???????} ???????build(); ???????father(); ???????dcc--; ???????int q; ???????scanf("%d",&q); ???????bool flag=0; ???????printf("Case %d:\n",shu); ???????for(int k=1;k<=q;k++) ???????{ ???????????scanf("%d%d",&x,&y); ???????????if(c[x]==c[y]) ???????????{ ???????????????flag=1; ??????????????} ???????????else{ ???????????????int p=lca(c[x],c[y]); ???????????????work(c[x],p); ???????????????work(c[y],p); ???????????} ???????????printf("%d\n",dcc); ???????} ???????puts(""); ??????} ??????return 0;}注意:memset要清空，dep[0]=-1;
POJ3694 Network
原文地址：https://www.cnblogs.com/Miracevin/p/9031484.html