Network

题意

一个无向图可以有重边，下面 个操作，每次在两个点间连接一条有向边，每次连接后整个无向图还剩下多少桥（注意是要考虑之前连了的边，每次回答是在上一次的基础之上）

分析

求出桥来之后缩点，缩点运用并查集实现，每一个点组用父亲节点代表。emm，好像就这样。

PS:

虽说楼上大佬说并查集实现更快，但我还是比 慢啊。我太菜了/kk

代码

#include<bits/stdc++.h>
#define ll long long
const int N=2e5+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int tot,nxt[N*2],point[N],v[N*2],num,dfn[N],low[N],stack_[N],ss,nn;
int belong[N],f[N],father[N],ans;
bool vis[N];

void cl()
{
    tot=0;memset(point,0,sizeof(point));
    memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low));
    nn=0;ss=0;num=0;ans=0;
}

void addline(int x,int y)
{
    nxt[++tot]=point[x];point[x]=tot;v[tot]=y;
    nxt[++tot]=point[y];point[y]=tot;v[tot]=x;   
}

int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}

void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++nn;vis[x]=1;stack_[++ss]=x;
    bool fff=0;
    for (int i=point[x];i;i=nxt[i])
    {
        if (v[i]==fa && !fff){fff=1; continue;}
        if (!dfn[v[i]])
        {
            father[v[i]]=x;
            tarjan(v[i],x);
            low[x]=min(low[x],low[v[i]]);
            if (low[v[i]]>dfn[x]) ans++;
            else f[find(v[i])]=find(x);
        }
        else low[x]=min(low[x],dfn[v[i]]);
    }
}

int lca(int x,int y)
{
    if (dfn[x]<dfn[y]) swap(x,y);
    while (dfn[x]>dfn[y])
    {
        int xx=find(x),ff=find(father[x]);
        if (xx!=ff) ans--,f[xx]=ff;
        x=father[x];
    }
    while (y!=x)
    {
        int xx=find(y),ff=find(father[y]);
        if (xx!=ff) ans--,f[xx]=ff;
        y=father[y];
    }
    return ans;
}

int main()
{
    int cnt=0,n,m,i,q;
    n=read();m=read();
    while(n&&m)
    {
        cl();int x,y;
        for (i=1;i<=m;i++)
        {
            x=read();y=read();
            addline(x,y);
        }
        for (i=1;i<=n;i++) f[i]=i;
        tarjan(1,0);
        q=read();
        printf("Case %d:\n",++cnt);
        for (i=1;i<=q;i++)
        {
            x=read();y=read();
            printf("%d\n",lca(x,y));
        }
        printf("\n");
        n=read();m=read();
    }
}