题意：
给定一个n个点m条边的无向图，q个操作，每个操作给（x，y）连边并询问此时图中的割边有多少条。（连上的边会一直存在）
n<=1e5,m<=2*10^5,q<=1e3,多组数据。
题解：
用tarjan求边双连通分量并缩点，缩点后组成一棵树，记录此时割边共有sum条。
连接(x,y)，设c[i]为缩点后i所在的新点（边双连通分量），则c[x]–>lca–>c[y]形成一个环，环上的所有边都不再是割边，走一遍并标记，如果遇到没标记过的就sum–。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std; 6
7 const int N=100010,M=200010,K=20; 8 int n,m,al,bl,sum,num,sl,cnt; 9 int afirst[N],bfirst[N],fa[N][K],dfn[N],low[N],is[N],c[N],s[N],dep[N]; 10 struct node{ 11 int x,y,tmp,next; 12 }a[2*M],b[2*M]; 13
14 int minn(int x,int y){return x<y ? x:y;} 15
16 void ins_a(int x,int y) 17 { 18 a[++al].x=x;a[al].y=y;a[al].tmp=0; 19 a[al].next=afirst[x];afirst[x]=al; 20 } 21
22 void ins_b(int x,int y) 23 { 24 b[++bl].x=x;b[bl].y=y; 25 b[bl].next=bfirst[x];bfirst[x]=bl; 26 } 27
28 void tarjan(int x) 29 { 30 dfn[x]=low[x]=++num; 31 s[++sl]=x; 32 for(int i=afirst[x];i;i=a[i].next) 33 { 34 if(a[i].tmp) continue; 35 a[i].tmp=1; 36 a[i%2==0 ? i-1:i+1].tmp=1; 37 int y=a[i].y; 38 if(!dfn[y]) 39 { 40 tarjan(y); 41 low[x]=minn(low[x],low[y]); 42 if(dfn[x]<low[y]) 43 { 44 sum++;//printf("%d -- > %d\n",x,y);
45 cnt++; 46 int z; 47 while(1) 48 { 49 z=s[sl--]; 50 c[z]=cnt; 51 if(z==y) break; 52 } 53 } 54 } 55 else low[x]=minn(low[x],dfn[y]); 56 } 57 } 58
59 void dfs(int x) 60 { 61 for(int i=bfirst[x];i;i=b[i].next) 62 { 63 int y=b[i].y; 64 if(y==fa[x][0]) continue; 65 fa[y][0]=x;dep[y]=dep[x]+1; 66 dfs(y); 67 } 68 } 69
70 void prepare_lca() 71 { 72 memset(fa,0,sizeof(fa)); 73 memset(dep,0,sizeof(dep)); 74 memset(is,0,sizeof(is)); 75 dep[1]=1; 76 dfs(1); 77 for(int j=1;j<=18;j++) 78 for(int i=1;i<=n;i++) 79 fa[i][j]=fa[fa[i][j-1]][j-1]; 80 } 81
82 int get_lca(int x,int y) 83 { 84 if(dep[x]<dep[y]) swap(x,y); 85 for(int i=18;i>=0;i--) 86 if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; 87 if(x==y) return x; 88 for(int i=18;i>=0;i--) 89 { 90 if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; 91 } 92 return fa[x][0]; 93 } 94
95 void del(int x,int y,int lca) 96 { 97 while(x!=lca) 98 { 99 if(!is[x]) sum--; 100 is[x]=1; 101 x=fa[x][0]; 102 } 103 while(y!=lca) 104 { 105 if(!is[y]) sum--; 106 is[y]=1; 107 y=fa[y][0]; 108 } 109 } 110
111 int main() 112 { 113 freopen("a.in","r",stdin); 114 int q,x,y,T=0; 115 while(1) 116 { 117 scanf("%d%d",&n,&m); 118 if(!n && !m) return 0; 119 printf("Case %d:\n",++T); 120 al=0;bl=0;sum=0; 121 memset(afirst,0,sizeof(afirst)); 122 memset(bfirst,0,sizeof(bfirst)); 123 num=0;sl=0;cnt=0; 124 memset(dfn,0,sizeof(dfn)); 125 memset(c,0,sizeof(c)); 126 for(int i=1;i<=m;i++) 127 { 128 scanf("%d%d",&x,&y); 129 ins_a(x,y);ins_a(y,x); 130 } 131 for(int i=1;i<=n;i++) 132 { 133 if(!dfn[i]) 134 { 135 tarjan(i); 136 if(sl) 137 { 138 cnt++; 139 for(int i=1;i<=sl;i++) c[s[i]]=cnt; 140 sl=0; 141 } 142 } 143 } 144
145 for(int i=1;i<=2*m;i++) 146 { 147 x=a[i].x,y=a[i].y; 148 if(c[x]!=c[y]) ins_b(c[x],c[y]); 149 } 150 // for(int i=1;i<=bl;i++) 151 // printf("%d -- > %d\n",b[i].x,b[i].y); 152 // for(int i=1;i<=n;i++) printf("c [ %d ] = %d\n",i,c[i]);
153 prepare_lca(); 154 scanf("%d",&q); 155 for(int i=1;i<=q;i++) 156 { 157 scanf("%d%d",&x,&y); 158 x=c[x];y=c[y]; 159 int lca=get_lca(x,y); 160 del(x,y,lca); 161 printf("%d\n",sum); 162 } 163 printf("\n"); 164 } 165 return 0; 166 }