无向图点双建立园方树,并且记录边在哪个点双之内
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pll; const int N=3e5+10; int h[N],e[N],ne[N],idx; int dfn[N],ins[N],low[N],w[N],times; int depth[N],fa[N],ans[N][25],fa_e[N]; int vcc[N]; stack<int> st,st_e; vector<int> g[N]; int n,m; int cnt; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void dfs(int u){ ins[u]=1; dfn[u]=low[u]=++times; int i; st.push(u); for(int i=h[u];i!=-1;i=ne[i]){ int v=e[i],id=w[i]; if(!dfn[v]){ fa[v] = u; fa_e[v] = id; st_e.push(id); dfs(v); low[u] = min(low[u], low[v]); //if(dfn[u] < low[v]) isce[v] = 1; if(dfn[u] <= low[v]){ ++cnt; while(1){ auto x = st.top(); g[cnt].push_back(x); g[x].push_back(cnt); ins[x] = 0; st.pop(); if(x == v) break; } g[cnt].push_back(u); g[u].push_back(cnt); while(1){ id = st_e.top(); st_e.pop(); vcc[id] = cnt; if(id==fa_e[v]) break; } } } else if(v != fa[u]){ low[u] = min(low[u], dfn[v]); if(dfn[v] < dfn[u]) st_e.push(id); } } } int vis[N]; void dfs2(int u){ vis[u] = 1; for(int j=1;j<=20;j++){ //if(depth[u] <= (1<<j)) //break; ans[u][j] = ans[ans[u][j-1]][j-1]; } int v; for(int k=0;k<g[u].size();k++){ v = g[u][k]; if(vis[v]) continue; ans[v][0] = u; depth[v] = depth[u] + 1; dfs2(v); } } int lca(int a,int b){ if(depth[a]<depth[b]) swap(a,b); int i; for(i=20;i>=0;i--){ if(depth[ans[a][i]]>=depth[b]){ a=ans[a][i]; } } if(a==b) return a; for(i=20;i>=0;i--){ if(ans[a][i]!=ans[b][i]){ a=ans[a][i]; b=ans[b][i]; } } return ans[a][0]; } int main(){ while(1){ scanf("%d%d", &n, &m); if(!m && !n) break; memset(fa, 0, sizeof(fa)); memset(ans, 0, sizeof(ans)); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(depth, 0, sizeof(depth)); //memset(inst, 0, sizeof(inst)); memset(vis, 0, sizeof(vis)); //memset(vdcc, 0, sizeof(vdcc)); memset(h,-1,sizeof h); times=0; cnt = n; int u,v; for(int i=1;i<=m;i++){ scanf("%d%d", &u, &v); add(u,v,i); add(v,u,i); } for(int i=1;i<=n;i++){ if(!dfn[i]){ dfs(i); depth[i] = 1; dfs2(i); } } int Q; scanf("%d",&Q); int x, y; while(Q--){ scanf("%d%d", &x, &y); x = vcc[x]; y = vcc[y]; int z = lca(x,y); printf("%d\n", (depth[x] + depth[y] - 2*depth[z])/2); } for(int i=1;i<=cnt;i++) g[i].clear(), g[i].clear(); } return 0; }