Network

题意

给定一张个点,条边的无向连通图，然后执行次操作,每次向图中添加一条边，并且询问图上桥的数量

前置芝士

  1. 无向图的割点和桥

    给定无向连通图图片说明
    1.若对于图片说明 ,从图中删去节点以及所有关联边之后，分裂为两个或两个不相连的子图，则称为的割点
    2.若对于图片说明 ,从图中删去边之后，分裂为两个不相连的子图，则称为的割边或桥

  2. 割边判定法则

    无向边是桥，当且仅当树上存在的一个子节点，满足：图片说明 。因为这说明从子节点开始走，不管走那一条边，都无法到达或比更早访问的节点。
    图片说明
    如果此时我们把绿边删去，那么图就会断成多个部分，因此他们就是割边。通过找到这些不同的连通块，把他们所成一个点，重新建图
    图片说明 

    inline void tarjan(int u,int idg)
{
 dfn[u]=low[u]=++cnt;

 for (int i=h[u];~i;i=las[i])
 {
     int v=to[i];
     if(!dfn[v])
     {
         tarjan(v,i);
         low[u]=min(low[u],low[v]);
         if(dfn[u]<low[v])
             eg[i]=eg[i^1]=1;
     }
     else if((idg^1)!=i)
         low[u]=min(low[u],dfn[v]);
     //求桥 
 }
}

  3. e-DCC

    即边双连通分量(极大边双连通子图)，若一张无向连通图不存在桥，则称其为“边双连通图”。求法很简单，因为已经求出了所有的桥，那么我们就找到不通过桥的能够连通的所有子图，把他们划分到一个连通块中。只需要在上面的代码上修改一下

    inline void tarjan(int u,int idg)
{
  stk[++tp]=u;
  dfn[u]=low[u]=++cnt;

  for (int i=h[u];~i;i=las[i])
  {
      int v=to[i];
      if(!dfn[v])
      {
          tarjan(v,i);
          low[u]=min(low[u],low[v]);
          if(dfn[u]<low[v])
              eg[i]=eg[i^1]=1;
      }
      else if((idg^1)!=i)
          low[u]=min(low[u],dfn[v]);
      //求桥 
  }

  if(low[u]==dfn[u])
  {
      ++tot;
      int y;

      do
      {
          y=stk[tp--];
          id[y]=tot;
      }while(y!=u);
  }
}

正题

  1. 先用Tarjan算法求出无向图所有的"边双连通分量"，并对每一个"e-DCC"缩点，得到一棵树，那么此时桥的数目就是所点后树的边数
  2. 一次考虑每一个加边操作，如果属于一个e-DCC，那么缩点后桥的数量不变；若他们属于不同的e-DCC，那么说明他们的缩点后的树上最短路径上的所有边都不再是"桥"，于是可以求出他们的LCA，从这些点一步一步跳的父节点并标记沿途的边，这里可以用并查集路径压缩优化。只要此时跳到的深度小于父节点，就不用再跳了。

代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

/*
    先求出所有的边双连通分量,缩点

连边,跑dfs,处理这棵无环树,在向上

查找桥时,可以并查集优化
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=2e5+10;

int tot,cnt,fa,fa2,tp;
int h[N],kp[N],id[N],f[20][N],stk[N];
int dfn[N],low[N],eg[N<<1],dep[N],fat[N];

int las[N<<1],to[N<<1];
int now[N<<1],des[N<<1];

queue<int>q;

inline void init()
{
    fa=0,fa2=0,cnt=0,tot=0;
    memset(las,0,sizeof(las));
    memset(to,0,sizeof(to));
    memset(now,0,sizeof(now));
    memset(des,0,sizeof(des));
    memset(h,-1,sizeof(h));
    memset(kp,-1,sizeof(kp));
    memset(dfn,0,sizeof(dfn));
    memset(eg,0,sizeof(eg));
}

inline void add(int x,int y)
{
    las[fa]=h[x];
    to[fa]=y;
    h[x]=fa++;
}

inline void adk(int x,int y)
{
    now[fa2]=kp[x];
    des[fa2]=y;
    kp[x]=fa2++;
}

inline void tarjan(int u,int idg)
{
    stk[++tp]=u;
    dfn[u]=low[u]=++cnt;

    for (int i=h[u];~i;i=las[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v])
                eg[i]=eg[i^1]=1;
        }
        else if((idg^1)!=i)
            low[u]=min(low[u],dfn[v]);
        //求桥 
    }

    if(low[u]==dfn[u])
    {
        ++tot;
        int y;

        do
        {
            y=stk[tp--];
            id[y]=tot;
        }while(y!=u);
    }
}

inline void dfs(int u,int v)
{
    dep[u]=dep[v]+1;
    f[0][u]=v;
    for (int i=1;i<=18;i++)
        f[i][u]=f[i-1][f[i-1][u]];

    for (int i=kp[u];~i;i=now[i])
    {
        int j=des[i];
        if(j==v) continue;

        dfs(j,u);
    }
}

inline int get(int x)
{
    if(x==fat[x]) return x;
    return fat[x]=get(fat[x]);
}

inline int Lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);

    for (int i=18;i>=0;i--)
        if(dep[f[i][x]]>=dep[y])
            x=f[i][x];
    if(x==y) return x;

    for (int i=18;i>=0;i--)
        if(f[i][x]!=f[i][y])
            x=f[i][x],y=f[i][y];

    return f[0][x];
}

int main()
{
    int T=0;int n,m,u,v;
    while(scanf("%d%d",&n,&m)&&n)
    {
        init();

        for (int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v),add(v,u);
        }
        //建边 
        for (int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i,0);
        //找强联通分量 

        for (int i=1;i<=n;i++)
            for (int j=h[i];~j;j=las[j])
            {
                v=to[j];
                if(id[i]==id[v]) continue;
                adk(id[i],id[v]);
            }dfs(1,0);

        T++;printf("Case %d:\n",T);
        int q,ans=tot-1;scanf("%d",&q);
        for (int i=1;i<=tot;i++) fat[i]=i;
        while(q--)
        {
            scanf("%d%d",&u,&v);

            if(id[u]!=id[v])
            {
                u=id[u],v=id[v];
                int lca=Lca(u,v);
                u=get(u);
                while(dep[lca]<dep[u])
                {
                    fat[u]=f[0][u];
                    ans--;
                    u=get(u);
                }

                v=get(v);
                while(dep[lca]<dep[v])
                {
                    fat[v]=f[0][v];
                    ans--;
                    v=get(v);
                }
            }
            printf("%d\n",ans);
        }
        puts("");
    }

    return 0;
}