题意：给你一个无向图，可能有重边，有q次询问，问你每次我添加一条边，添加后这个图还有多少个桥
解题思路：首先先把所有没有割边的点对缩成一个联通块，无向图一般并查集判环，然后就得到一个割边树，给你一条新边，找到这条边两个端点的所属的联通块，如果这两个端点属于用一个联通块，那么没有作用，属于不同的联通块的时候，找到他们的lca，路径上有多少边，就减去多少割边，然后成为一个新的联通块，具体见代码
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstring>
using namespace std;
const int maxn=;
struct Edge
{
int next;int to;int id;
}edge[maxn<<];
int head[maxn],cnt,dfn[maxn],low[maxn];
int fa[maxn],pre[maxn],ans,step,n,m;
void init()
{
memset(head,-,sizeof(head));cnt=ans=step=;
for(int i=;i<=n;i++)
fa[i]=i;
memset(dfn,,sizeof(dfn));memset(low,,sizeof(low)); }
int findf(int u)
{
if(fa[u]==u)
return u;
else
{
fa[u]=findf(fa[u]);
return fa[u];
}
}
bool join(int x,int y)
{
int t1=findf(x);
int t2=findf(y);
if(t1==t2)
return false;
else
{
fa[t2]=t1;
return true;
}
}
void add(int u,int v,int id)//id是用来判是否有重边的
{
edge[cnt].next=head[u];edge[cnt].to=v;edge[cnt].id=id;head[u]=cnt++;
edge[cnt].next=head[v];edge[cnt].to=u;edge[cnt].id=id;head[v]=cnt++;
}
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++step;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
int id=edge[i].id;
if(fa==id)
continue;
if(!dfn[v])
{
pre[v]=u;//记录他的父亲结点
tarjan(v,id);
low[u]=min(low[v],low[u]);
if(dfn[u]<low[v])
{
ans++;
}
else
{
join(u,v);//不是割边就合并
} }
else
{
low[u]=min(low[u],dfn[v]);
}
}
}
void lca(int u,int v)
{
if(findf(u)==findf(v))
return;
if(dfn[v]<dfn[u])//根据之前pre数组，从小的位置开始
swap(u,v);
while(dfn[v]>dfn[u])
{
if(join(pre[v],v))//路径上的割边全部合并
{
ans--;
}
v=pre[v];
}
while(u!=v)//如果是1的另一个子树中，因为上一段最多判到1，还需要判另一半
{
if(join(pre[u],u))
ans--;
u=pre[u];
}
}
int main()
{
int x,y;
int k,cot;
cot=;
while(scanf("%d%d",&n,&m)&&n&&m)
{
cot++;
init();
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);add(x,y,i);
}
tarjan(,);
pre[]=;
printf("Case %d:\n",cot);
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&x,&y);
lca(x,y);
printf("%d\n",ans);
}
}
}
；