題意： 給出一個無向連通圖，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;

轉載于:https://www.cnblogs.com/Miracevin/p/9031484.html

總結

以上是生活随笔為你收集整理的POJ3694 Network的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。