题意抽象为：
给一个无向图和一些询问
对于每一次询问：
每次询问都会在图上增加一条边
对于每一次询问输出此时图上桥的个数。
桥的定义：删除该边后原图变为多个连通块。
数据规模：点数N(1 ≤ N ≤ 100,000) ，边数M(N - 1 ≤ M ≤ 200,000)，询问数Q ( 1 ≤ Q ≤ 1,000)
先跑一遍tarjan，对边双连通分枝缩一下点。
再维护lca即可。
AC代码：
#include<cstdio> #include<cstring> #include<queue> #define rep(i,a,b) for(int i=a;i<=b;++i) using namespace std; const int MAXV=110000; const int MAXE=410000; int DFN[MAXV],low[MAXV],par[MAXV],label[MAXV]; int pointer[MAXV]; int tot,cnt,m,n,Bcnt,ans; vector<int> graph[MAXV]; struct Edge { int to,next; bool vis; Edge() {} Edge(int b,int nxt,int flag) {to=b,next=nxt,vis=flag;} }edge[MAXE]; inline void addedge(int a,int b) { edge[tot]=Edge(b,pointer[a],0); pointer[a]=tot++; edge[tot]=Edge(a,pointer[b],0); pointer[b]=tot++; } void init() { tot=0; cnt=0;Bcnt=0; memset(pointer,-1,sizeof(pointer)); memset(label,0,sizeof(label)); memset(DFN,0,sizeof(DFN)); } void tarjan(int u,int pre) { DFN[u]=low[u]=++cnt; for(int j=pointer[u];j!=-1;j=edge[j].next) { int v=edge[j].to; if(edge[j].vis) continue; edge[j].vis=edge[j^1].vis=1; if(!DFN[v]) { par[v]=j; tarjan(v,u); if(low[v]<low[u]) low[u]=low[v]; } else if(low[u]>DFN[v]) low[u]=DFN[v]; } } void part(int u) { label[u]=Bcnt; for(int j=pointer[u];j!=-1;j=edge[j].next) { int v=edge[j].to; if(!label[v]&&edge[j].vis) part(v); } } int dep[MAXV]; int father[MAXV],a[MAXV]; void lca_bfs(int S) { rep(i,1,Bcnt) dep[i]=-1; queue<int>q; dep[S]=0; q.push(S); father[S]=S; while(!q.empty()) { int u=q.front();q.pop(); for(int i=0;i<graph[u].size();++i) { int v=graph[u][i]; if(dep[v]==-1) { dep[v]=dep[u]+1; a[v]=1; father[v]=u; q.push(v); } } } } void lca(int u,int v) { if(dep[u]>dep[v]) swap(u,v); while(dep[u]<dep[v]) { if(a[v]) { ans--; a[v]=0; } v=father[v]; } while(u!=v) { if(a[v]) { ans--; a[v]=0; } v=father[v]; if(a[u]) { ans--; a[u]=0; } u=father[u]; } } int main() { // freopen("in.txt","r",stdin); int icase=0; while(scanf("%d%d",&n,&m)&&m&&n) { int a,b; init(); rep(i,1,m) { scanf("%d%d",&a,&b); addedge(a,b); } tarjan(1,1); int tmp,u; rep(i,2,n) { tmp=par[i]^1; u=edge[tmp].to; if(DFN[u]<low[i]) { edge[tmp].vis=edge[tmp^1].vis=0; } } rep(i,1,n) { if(!label[i]) { Bcnt++; part(i); } } ans=Bcnt-1; rep(i,2,n) { if(!edge[par[i]].vis) { tmp=par[i]^1; u=edge[tmp].to; graph[label[u]].push_back(label[i]); graph[label[i]].push_back(label[u]); } } lca_bfs(1); int v,q; scanf("%d",&q); printf("Case %d: ",++icase); rep(i,1,q) { scanf("%d%d",&u,&v); lca(label[u],label[v]); printf("%d ",ans); } printf(" "); } return 0; }