[hdu2460]network(依次连边并询问图中割边数量) tarjan边双联通分量+lca

题意：

给定一个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--。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int N=,M=,K=;

 int n,m,al,bl,sum,num,sl,cnt;

 int afirst[N],bfirst[N],fa[N][K],dfn[N],low[N],is[N],c[N],s[N],dep[N];

 struct node{

     int x,y,tmp,next;

 }a[*M],b[*M];

 int minn(int x,int y){return x<y ? x:y;}

 void ins_a(int x,int y)

 {

     a[++al].x=x;a[al].y=y;a[al].tmp=;

     a[al].next=afirst[x];afirst[x]=al;

 }

 void ins_b(int x,int y)

 {

     b[++bl].x=x;b[bl].y=y;

     b[bl].next=bfirst[x];bfirst[x]=bl;

 }

 void tarjan(int x)

 {

     dfn[x]=low[x]=++num;

     s[++sl]=x;

     for(int i=afirst[x];i;i=a[i].next)

     {

         if(a[i].tmp) continue;

         a[i].tmp=;

         a[i%== ? i-:i+].tmp=;

         int y=a[i].y;

         if(!dfn[y])

         {

             tarjan(y);

             low[x]=minn(low[x],low[y]);

             if(dfn[x]<low[y])

             {

                 sum++;//printf("%d -- > %d\n",x,y);

                 cnt++;

                 int z;

                 while()

                 {

                     z=s[sl--];

                     c[z]=cnt;

                     if(z==y) break;

                 }

             }

         }

         else low[x]=minn(low[x],dfn[y]);

     }

 }

 void dfs(int x)

 {

     for(int i=bfirst[x];i;i=b[i].next)

     {

         int y=b[i].y;

         if(y==fa[x][]) continue;

         fa[y][]=x;dep[y]=dep[x]+;

         dfs(y);

     }

 }

 void prepare_lca()

 {

     memset(fa,,sizeof(fa));

     memset(dep,,sizeof(dep));

     memset(is,,sizeof(is));

     dep[]=;

     dfs();

     for(int j=;j<=;j++)

         for(int i=;i<=n;i++)

             fa[i][j]=fa[fa[i][j-]][j-];

 }

 int get_lca(int x,int y)

 {

     if(dep[x]<dep[y]) swap(x,y);

     for(int i=;i>=;i--)

         if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];

     if(x==y) return x;

     for(int i=;i>=;i--)

     {

         if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

     }

     return fa[x][];

 }

 void del(int x,int y,int lca)

 {

     while(x!=lca)

     {

         if(!is[x]) sum--;

         is[x]=;

         x=fa[x][];

     }

     while(y!=lca)

     {

         if(!is[y]) sum--;

         is[y]=;

         y=fa[y][];

     }

 }

 int main()

 {

     freopen("a.in","r",stdin);

     int q,x,y,T=;

     while()

     {

         scanf("%d%d",&n,&m);

         if(!n && !m) return ;

         printf("Case %d:\n",++T);

         al=;bl=;sum=;

         memset(afirst,,sizeof(afirst));

         memset(bfirst,,sizeof(bfirst));

         num=;sl=;cnt=;

         memset(dfn,,sizeof(dfn));

         memset(c,,sizeof(c));

         for(int i=;i<=m;i++)

         {

             scanf("%d%d",&x,&y);

             ins_a(x,y);ins_a(y,x);

         }

         for(int i=;i<=n;i++)

         {

             if(!dfn[i])

             {

                 tarjan(i);

                 if(sl)

                 {

                     cnt++;

                     for(int i=;i<=sl;i++) c[s[i]]=cnt;

                     sl=;

                 }

             }

         }

         for(int i=;i<=*m;i++)

         {

             x=a[i].x,y=a[i].y;

             if(c[x]!=c[y]) ins_b(c[x],c[y]);

         }

         // for(int i=1;i<=bl;i++)

             // printf("%d -- > %d\n",b[i].x,b[i].y);

         // for(int i=1;i<=n;i++) printf("c [ %d ] = %d\n",i,c[i]);

         prepare_lca();

         scanf("%d",&q);

         for(int i=;i<=q;i++)

         {

             scanf("%d%d",&x,&y);

             x=c[x];y=c[y];

             int lca=get_lca(x,y);

             del(x,y,lca);

             printf("%d\n",sum);

         }

         printf("\n");

     }

     return ;

 }