给我们一个图，然后有q次加边的操作，问每次加完边之后有多少个桥存在
首先用dfs求出所有的桥，然后dfs的过程中生成了一棵dfs树，该树有的边是桥，有的不是，用bridge[v] = true , 表示v与fa[v]的连边是桥
当加入一个边u,v后， u,v,lca(u,v)上的边从割边变成了非割边。
至于lca，我们可以用dfs过程中的dfn标号来向上回溯。
因为dfn[u] > dfn[lca(u,v)], dfn[v] > dfn[lca(u,v])
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <functional>
using namespace std; const int N = +;
int head[N],next[N*],to[N*],e;
int dfn[N],low[N],dfs_clock,cut,bridge[N],pre[N]; void init(int n)
{
e = dfs_clock = cut = ;
memset(head,-,sizeof(head));
for(int i=;i<=n;++i)
{
fa[i] = i;
dfn[i] = low[i] = bridge[i] = ;
}
}
void addEdge(int u, int v)
{
to[e] = v;
next[e] = head[u];
head[u] = e++;
} void tarjan(int u, int f)
{
dfn[u] = low[u] = ++dfs_clock;
bool flag = false;
for(int i=head[u]; i!=-; i=next[i])
{
int v = to[i];
if(v==f && !flag)
{
flag=true;
continue;
}
if(dfn[v]==)
{
pre[v] = u;
tarjan(v,u);
}
low[u] = min(low[v],low[u]);
if(low[v] > dfn[u])
{
bridge[v] = true;
cut++;
}
}
} void lca(int u, int v)
{
if(dfn[u] < dfn[v])
swap(u,v);
while(dfn[u] > dfn[v])//回溯完后u就是lca
{ if(bridge[u])
{
cut--;
bridge[u] = false;
}
u = pre[u];
}
while(dfn[u] < dfn[v])
{ if(bridge[v])
{
cut--;
bridge[v] = false;
}
v = pre[v];
}
}
int main()
{
int n,m;
int u,v;
int tcase = ;
while(scanf("%d%d",&n,&m),n+m)
{
init(n);
for(int i=;i<=m;++i)
{
scanf("%d%d",&u,&v);
addEdge(u,v);addEdge(v,u);
}
printf("Case %d:\n",tcase++);
tarjan(,-);
int q;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&u,&v);
lca(u,v);
printf("%d\n",cut);
}
puts("");
}
return ;
}