题意：有一个网络有一些边相互连接，现在有Q次操作，求每次操作后的桥的个数
分析：开始竟然不知道还有LCA这么个东西.......
*****************************************************************
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; const int MAXN = 1e5+; /********添加边*************/
struct Edage{int v, next, used;}e[MAXN<<];
int Head[MAXN], cnt;
void AddEdge(int u, int v)
{
e[cnt].v = v;
e[cnt].next = Head[u];
e[cnt].used = false;
Head[u] = cnt++;
}
/***********Tarjan算法变量**********/
int dfn[MAXN], low[MAXN], Index;
int fa[MAXN];
int isbridge[MAXN], nbridge; void InIt(int N)
{
cnt = Index = nbridge = ; for(int i=; i<=N; i++)
{
Head[i] = -;
dfn[i] = ;
isbridge[i] = false;
}
}
void Tarjan(int u, int father)
{
int v; low[u] = dfn[u] = ++Index;
fa[u] = father; for(int j=Head[u]; j!=-; j=e[j].next)
{
if(e[j].used == false)
{
e[j].used = e[j^].used = true;
v = e[j].v;
if( !dfn[v] )
{
Tarjan(v, u);
low[u] = min(low[u], low[v]); if( low[v] > dfn[u] )
{
isbridge[v] = true;
nbridge++;
}
}
else
low[u] = min(low[u], dfn[v]);
}
}
} void LCA(int u, int v)
{
if(dfn[u] < dfn[v])
swap(u, v); while(dfn[u] > dfn[v])
{
if(isbridge[u])nbridge--;
isbridge[u] = false;
u = fa[u];
} while(u != v)
{
if(isbridge[u])nbridge--;
if(isbridge[v])nbridge--;
isbridge[u] = isbridge[v] = false; u = fa[u], v = fa[v];
}
} int main()
{
int N, M, t=; while(scanf("%d%d", &N, &M), N+M)
{
int u, v; InIt(N); while(M--)
{
scanf("%d%d", &u, &v);
AddEdge(u, v);
AddEdge(v, u);
} Tarjan(, ); scanf("%d", &M); printf("Case %d:\n", t++);
while(M--)
{
scanf("%d%d", &u, &v);
LCA(u, v);
printf("%d\n", nbridge);
} printf("\n");
} return ; }