题意:
给一个无向图,有q次插入操作,每次加入一条边,求每次插入后图中的桥有多少。
思路:
缩点成一棵树后每次插入操作都查询一次LCA,沿路更新整个图中的桥数ans。
//poj 3694
//sepNINE
#include <iostream>
#include <stack>
using namespace std;
const int maxN=100024;
const int maxM=200024;
struct Edge
{int v,next;
}edge[maxM*2],treeEdge[maxM*2];
int n,m,e,treeE,t,cnt,cases,ans;
int head[maxN],treeHead[maxN],dfn[maxN],low[maxN],inStack[maxN],par[maxN],belong[maxN];
int bridge[maxN],pre[maxN],level[maxN],vis[maxN];
stack<int> mystack;
void addEdge(int a,int b)
{edge[e].v=b;edge[e].next=head[a];head[a]=e++;edge[e].v=a;edge[e].next=head[b];head[b]=e++;
}
void addTreeEdge(int a,int b)
{treeEdge[treeE].v=b;treeEdge[treeE].next=treeHead[a];treeHead[a]=treeE++;treeEdge[treeE].v=a;treeEdge[treeE].next=treeHead[b];treeHead[b]=treeE++;
} void tarjan(int h)
{inStack[h]=1;mystack.push(h); dfn[h]=low[h]=++t;for(int i=head[h];i!=-1;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){par[v]=h;tarjan(v);low[h]=min(low[h],low[v]);}else if(inStack[v]&&v!=par[h]){low[h]=min(low[h],dfn[v]); } }if(low[h]==dfn[h]){int k;++cnt;do{k=mystack.top();belong[k]=cnt;mystack.pop();inStack[k]=0; }while(low[k]!=dfn[k]);}
}void tree_dfs(int u,int dep)
{level[u]=dep;vis[u]=1; for(int i=treeHead[u];i!=-1;i=treeEdge[i].next){int v=treeEdge[i].v;if(vis[v]==0&&v!=pre[u]){bridge[v]=1;pre[v]=u;tree_dfs(v,dep+1);}}
}void update(int a,int b)
{while(level[a]>level[b]){if(bridge[a]==1){bridge[a]=0;--ans;}a=pre[a]; }while(level[a]<level[b]){if(bridge[b]==1){bridge[b]=0;--ans;}b=pre[b];}while(a!=b){if(bridge[a]==1){bridge[a]=0;--ans;}if(bridge[b]==1){bridge[b]=0;--ans;}a=pre[a];b=pre[b];}
}void solve()
{memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(inStack,0,sizeof(inStack));memset(belong,0,sizeof(belong));while(!mystack.empty()) mystack.pop();for(int i=1;i<=n;++i)if(!dfn[i]){par[i]=-1;tarjan(i); }for(int i=1;i<=n;++i)for(int j=head[i];j!=-1;j=edge[j].next){int u=belong[i],v=belong[edge[j].v];if(u!=v)addTreeEdge(u,v); }printf("Case %d:\n",++cases);memset(vis,0,sizeof(vis));memset(pre,0,sizeof(pre));memset(bridge,0,sizeof(bridge));int q;pre[belong[1]]=-1;tree_dfs(belong[1],1); ans=cnt-1;scanf("%d",&q);while(q--){int x,y;scanf("%d%d",&x,&y); if(belong[x]==belong[y])printf("%d\n",ans);else{update(belong[x],belong[y]);printf("%d\n",ans);} }printf("\n");
}int main()
{cases=0;while(scanf("%d%d",&n,&m)==2){if(n==0) break;t=0;e=0;cnt=0;treeE=0;memset(head,-1,sizeof(head));memset(treeHead,-1,sizeof(treeHead)); while(m--){int a,b;scanf("%d%d",&a,&b);addEdge(a,b);} solve();}return 0;
}
代码: