题意：
给定n个点m条边的无向图
Q个询问：
问加上这条边后图中还有多少桥。
注意询问不是独立的（加了边在后面都有效）
思路：
先缩点得到缩点树，加上一条边后[u, LCA(u,v), v] 成环，则删掉这里的点，并把集合向上合并
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <queue>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define inf 107374182
#define ll int
using namespace std;
#define N 100100
//N为点
#define M 200100
struct Edge{
int from, to, nex;
bool cut;
}edge[M*2];
int head[N], edgenum;
void addedge(int u, int v){
Edge E={u,v,head[u],false};
edge[ edgenum ] = E;
head[u] = edgenum++;
}
int n, m;
int dfn[N], low[N], tarjan_time, tar, Stack[N*5], top;
int Belong[N];
bool iscut[N];
void tarjan(int u, int fa){
dfn[u] = low[u] = ++tarjan_time;
Stack[++top] = u;
int child = 0, flag = 1;
for(int i = head[u]; ~i; i = edge[i].nex)
{
int v = edge[i].to;
if(flag && v==fa){flag = 0; continue;}
if(!dfn[v])
{
child++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u])
{
iscut[u] = true;
if(low[v]>dfn[u])
edge[i].cut = edge[i^1].cut = true;
}
}
else low[u] = min(low[u], dfn[v]);
}
if(child == 1 && fa<0)iscut[u] = false;
if(low[u] == dfn[u])
{
tar++;
do
{
Belong[ Stack[top] ] = tar;
}while(Stack[top--] != u);
}
}
void init(){
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(iscut, 0, sizeof(iscut));
memset(Belong, -1, sizeof(Belong));
tarjan_time = 0;
top = 0;
tar = 0;
tarjan(1,1);
}
vector<int>G[N];
const int MAXN = 101000;
int rmq[2*MAXN];//rmq数组，就是欧拉序列对应的深度序列
vector<int>son[N];
int Father[N];
struct ST
{
int mm[2*MAXN];
int dp[2*MAXN][20];//最小值对应的下标
void init(int n)
{
mm[0] = -1;
for(int i = 1;i <= n;i++)
{
mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];
dp[i][0] = i;
}
for(int j = 1; j <= mm[n];j++)
for(int i = 1; i + (1<<j) - 1 <= n; i++)
dp[i][j] = rmq[dp[i][j-1]] < rmq[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
}
int query(int a,int b)//查询[a,b]之间最小值的下标
{
if(a > b)swap(a,b);
int k = mm[b-a+1];
return rmq[dp[a][k]] <= rmq[dp[b-(1<<k)+1][k]]?dp[a][k]:dp[b-(1<<k)+1][k];
}
};
int F[MAXN*2];//欧拉序列，就是dfs遍历的顺序，长度为2*n-1,下标从1开始
int P[MAXN];//P[i]表示点i在F中第一次出现的位置
int cnt;
ST st;
int deep[N];
void dfs(int u,int pre,int dep)
{
F[++cnt] = u;
rmq[cnt] = dep;
P[u] = cnt;
for(int i = 0;i <G[u].size(); i++)
{
int v = G[u][i];
if(v == pre)continue;
dfs(v,u,dep+1);
F[++cnt] = u;
rmq[cnt] = dep;
son[u].push_back(v);
Father[v] = u;
deep[v] = deep[u]+1;
}
}
void LCA_init(int root,int node_num)//查询LCA前的初始化
{
cnt = 0;
dfs(root,root,0);
st.init(2*node_num-1);
}
int query_lca(int u,int v)//查询u,v的lca编号
{
return F[st.query(P[u],P[v])];
}
int f[N];
int find(int x){return x==f[x]?x:f[x] = find(f[x]);}
void Union(int x, int y){
int fx = find(x), fy = find(y);
if(fx==fy)return ;
if(deep[fx]<deep[fy])swap(fx,fy);
f[fx] = fy;
}
int main(){
int i, j, u, v, Cas = 1, Q;
while(scanf("%d %d",&n,&m),n+m){
printf("Case %d:\n", Cas++);
for(i=0;i<=n;i++)f[i]=i;
memset(head, -1, sizeof(head)), edgenum = 0;
while(m--)
{
scanf("%d %d",&u,&v);
addedge(u,v); addedge(v,u);
}
init();
for(i=0;i<=tar;i++)G[i].clear();
for(i=0;i<edgenum;i++){
u = Belong[edge[i].from], v = Belong[edge[i].to];
if(u!=v)G[u].push_back(v);
}
for(i = 0;i<=tar;i++)son[i].clear();
Father[1] = 1;
deep[1] = 0;
LCA_init(1,tar);
int now = tar-1;
scanf("%d",&Q);
while(Q--)
{
scanf("%d %d",&u,&v);if(now==0){puts("0");continue;}
u = Belong[u], v =Belong[v];
int fa = query_lca(u, v);
fa = find(fa);
u = find(u);
v = find(v);
while(u!=fa){
now--;
f[u] = fa;
u = Father[u];
u = find(u);
}
while(v!=fa){
now--;
f[v] = fa;
v = Father[v];
v = find(v);
}
printf("%d\n", now);
}
}
return 0;
}