Network题解

题意：

给一张n个点m条边的无向连通图，然后是q次连边操作（n<=1e5,m<=2e5,q<=1e3）

边双连通图：一张无向连通图不存在桥。
边双连通分量：无向连通图的极大边双连通子图。

思路

首先是把桥都给找出来。
然后思考怎样连两点会对答案有影响。
如果两点都在边双连通分量内，对答案无影响。
否则两点路径上不再有桥，即把路径上的桥的标记取消，答案减少。

做法：

对每个边双连通分量缩点，最后缩成一棵树，
找lca从下到上取消桥标记，统计答案。（q小可以暴力修改）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e5+10,t=20;
int len1=1,len2=0,h1[M],h2[M],total=0;
struct bian{int y,gg;}b1[M<<1],b2[M<<1];
bool bridge[M<<1];
int dfn[M],low[M],num=0;
void tarjan(int x,int lst)
{
    dfn[x]=low[x]=++num;
    for(int i=h1[x];i;i=b1[i].gg)
    {
        int y=b1[i].y;
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y])bridge[i]=bridge[i^1]=1;
        }
        else if(i!=(lst^1))low[x]=min(low[x],dfn[y]);
    }
}
int now=0,c[M],f[M][21],dep[M],tt[M];
void dfs1(int x)
{
    c[x]=now;
    for(int i=h1[x];i;i=b1[i].gg)
    {
        int y=b1[i].y;
        if(c[y]||bridge[i])continue;
        dfs1(y);
    }
}

void dfs2(int x)
{
    for(int i=h2[x];i;i=b2[i].gg)
    {
        int y=b2[i].y;
        if(f[x][0]==y)continue;
        f[y][0]=x;tt[y]=i;
        dep[y]=dep[x]+1;
        for(int j=1;j<=t;j++)
            f[y][j]=f[f[y][j-1]][j-1];
        dfs2(y);
    }
}

int get_lca(int x,int y)
{
    if(dep[x]<dep[y]){x^=y;y^=x;x^=y;}
    for(int i=t;i>=0;i--)
    if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return y;
    for(int i=t;i>=0;i--)
    if(dep[f[x][i]]!=dep[f[y][i]])x=f[x][i],y=f[y][i];
    return f[x][0];
}
void change(int x,int y)
{
    for(int i=x;i!=y;i=f[i][0])
    {
        //printf("!!%d %d\n",i,tt[i]);
        if(bridge[tt[i]])bridge[tt[i]]=bridge[tt[i]^1]=0,total--;
    }
}
void ins(int x,int y)
{
    b1[++len1].y=y;b1[len1].gg=h1[x];h1[x]=len1;
}

void add(int x,int y)
{
    b2[++len2].y=y;b2[len2].gg=h2[x];h2[x]=len2;
}
int n,m;
void solve()
{
    len1=1;len2=total=num=now=0;
    memset(bridge,0,sizeof(bridge));
    memset(h1,0,sizeof(h1));
    memset(h2,0,sizeof(h2));
    memset(f,0,sizeof(f));
    memset(dfn,0,sizeof(dfn));
    memset(c,0,sizeof(c));
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d %d",&x,&y);
        ins(x,y);ins(y,x);
    }
    tarjan(1,0);
    for(int i=1;i<=n;i++)
    if(!c[i])++now,dfs1(i);
    memset(bridge,0,sizeof(bridge));
    for(int i=2;i<=len1;i++)
    {
        int x=b1[i^1].y,y=b1[i].y;
        if(c[x]==c[y])continue;
        add(c[x],c[y]);bridge[len2]=1;
    }
    total=now-1;
    dep[1]=1;
    dfs2(1);
    int q;scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int x,y;scanf("%d %d",&x,&y);
        if(c[x]==c[y])printf("%d\n",total);
        else
        {
            int lca=get_lca(c[x],c[y]);
            change(c[x],lca);change(c[y],lca);
            printf("%d\n",total);
        }
    }
}
int main()
{
    int t=0;
    while(scanf("%d %d",&n,&m)&&n)
    {
        printf("Case %d:\n",++t);solve();printf("\n");
    }
    return 0;
}