主体思路:建图-割边-边双连通分量-缩点-lca并计数-输出
(具体实现细节在注释中有说明)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+5,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Edge{int ver,next; }edge[maxn],edgec[maxn];
int n,m,tot,head[maxn],cnt,num,dfn[maxn],low[maxn],c[maxn],
head1[maxn],bridge[maxn],dcc,tc,pre[maxn],verbri[maxn];//桥上的点
void add(int u,int v){
edge[++tot].ver=v; edge[tot].next=head[u]; head[u]=tot;
}
void addc(int u,int v){
edgec[++tc].ver=v; edgec[tc].next=head1[u]; head1[u]=tc;
}
void tarjan(int x,int inedge){
dfn[x]=low[x]=++num;
for(int i=head[x],y;i;i=edge[i].next){
if(!dfn[y=edge[i].ver]){
tarjan(y,i); pre[y]=x;//记录父节点
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x]) //只在桥的子节点位置进行标记
bridge[i]=bridge[i^1]=verbri[y]=1;
}else if(i!=(inedge^1)){
low[x]=min(low[x],dfn[y]);
}
}
}
void dfs(int x){
c[x]=dcc;
for(int i=head[x],y;i;i=edge[i].next){
if(c[y=edge[i].ver]||bridge[i]) continue;
dfs(y);
}
}
int lca(int u,int v){ //求u,v的最近公共祖先
int cnt1=0;
while(dfn[u]>dfn[v]){ //两次while的目的是使uv爬到同一个枝干上
if(verbri[u]) cnt1++,verbri[u]=0;
u=pre[u];
}
while(dfn[v]>dfn[u]){
if(verbri[v]) cnt1++,verbri[v]=0;
v=pre[v];
}
while(u!=v){ //在同一个枝干dfn小的不断向上挪,相等的位置就是祖先
if(verbri[u]) cnt1++,verbri[u]=0;
if(verbri[v]) cnt1++,verbri[v]=0;
if(dfn[u]>dfn[v]) u=pre[u];
if(dfn[v]>dfn[u]) v=pre[v];
}return cnt1;
}
//建图-割边-边双连通分量-缩点-lca并计数-输出
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
while(cin>>n>>m,n||m){
tot=1; //初始化为可以进行成对变换
memset(head,0,sizeof(head));
memset(head1,0,sizeof(head1));
memset(dfn,0,sizeof(dfn));
memset(c,0,sizeof(c));
memset(bridge,0,sizeof(bridge));
memset(low,0,sizeof(low));
memset(verbri,0,sizeof(verbri));
for(int i=1;i<=n;i++) pre[i]=i;
while(m--){ //建图
int a,b; cin>>a>>b;
add(a,b); add(b,a);
}
for(int i=1;i<=n;i++){ //求割边
if(!dfn[i]) tarjan(i,0);
}
for(int i=1;i<=n;i++){ //双连通分量
if(!c[i]){
++dcc;
dfs(i);
}
}
tc=1; // //缩点并构建树
for(int i=2;i<=tot;i++){
int x=edge[i].ver,y=edge[i^1].ver;
if(c[x]==c[y]) continue;
addc(c[x],c[y]);//缩点并构建树
} int ans=tc/2;//桥的数目
int q; cin>>q;
cout<<"Case "<<++cnt<<":\n";
while(q--){ //开始询问
int a,b; cin>>a>>b;
if(c[a]!=c[b])
ans-=lca(a,b);
cout<<ans<<'\n';
} cout<<'\n'; //空行
}
return 0;
}