叫network的题真是多。。。
思路：先一次tarjan缩点，得到一颗树，每次 加边，两个端点到它们的lca之间的边都不再是桥，所以每一次我们都可以通过暴力求出lca，然后统计出少了多少条桥，但是暴力统计时，会遇到某些边在之前就不是桥的情况，我们用并查集来跳过这些边（每一次加边就把lca路径上的点都合并到一个集合里去，这里根用最上面的点，到时如果遇到这种点，直接可以跳到它们的根上去）
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int maxn=110010; const int maxm=210010; int head[maxn]; int head2[maxn]; int DFN[maxn]; int low[maxn]; int deep[maxn]; int fa[maxn]; int block[maxn]; int pre[maxn]; int st[maxn]; int instack[maxn]; int tot,tot2,top,ord,sccnum,icase; struct node { int next,to,id; }edge[maxm<<2],edge2[maxm<<2]; void init() { memset(DFN,-1,sizeof(DFN)); memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); memset(low,0,sizeof(low)); memset(instack,0,sizeof(instack)); tot=tot2=ord=sccnum=top=0; } void addedge(int u,int v,int w) { edge[tot].to=v; edge[tot].id=w; edge[tot].next=head[u]; head[u]=tot++; } void addedge2(int u,int v) { edge2[tot2].to=v; edge2[tot2].next=head2[u]; head2[u]=tot2++; } int find(int x) { if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void dfs(int u,int f,int d) { pre[u]=f; deep[u]=d; for(int i=head2[u];i!=-1;i=edge2[i].next) { int v=edge2[i].to; if(v==f) continue; dfs(v,u,d+1); } } void tarjan(int u,int x) { DFN[u]=low[u]=++ord; instack[u]=1; st[top++]=u; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(edge[i].id==x) continue; if(DFN[v]==-1) { tarjan(v,edge[i].id); low[u]=min(low[u],low[v]); } else if(instack[v]) low[u]=min(low[u],DFN[v]); } int v; if(DFN[u]==low[u]) { ++sccnum; do { v=st[--top]; instack[v]=0; block[v]=sccnum; }while(v!=u); } } int LCA(int a,int b) { while(a!=b) { if(deep[a]>deep[b]) a=pre[a]; else if(deep[a]<deep[b]) b=pre[b]; else { a=pre[a]; b=pre[b]; } a=find(a); b=find(b); } return a; } void solve(int n) { tarjan(1,-1); for(int u=1;u<=n;u++) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(block[u]==block[v]) continue; addedge2(block[u],block[v]); } } for(int i=1;i<=sccnum;i++) fa[i]=i; int cnt=sccnum-1; dfs(1,-1,0); int q,a,b,lca; scanf("%d",&q); printf("Case %d:\n", icase++); while(q--) { scanf("%d%d",&a,&b); a=block[a]; b=block[b]; if(a==b) { printf("%d\n",cnt); continue; } a=find(a); b=find(b); lca=LCA(a,b); int x=0; while(a!=lca) { x++; fa[a]=lca; a=pre[a]; a=find(a); } while(b!=lca) { x++; fa[b]=lca; b=pre[b]; b=find(b); } cnt-=x; printf("%d\n",cnt); } } int main() { int n,m; int u,v; icase=1; while(scanf("%d%d",&n,&m)!=EOF) { if(!n&&!m) break; init(); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); addedge(u,v,i); addedge(v,u,i); } solve(n); puts(""); } return 0; }
