题意
给定一张 (n) 个点 (m) 条边的无向图，(q) 次询问，每次询问两边之间的必经之点个数。
思路
求两点之间必经之边的个数用的是边双缩点，再求树上距离。而对比边双和点双之后，我们不难发现点和边之间的对应关系，边双分量和点双分量的性质很多都是对称的。
| 边双 | 点双 |
|---|---|
| 两点之间至少有两条不共边的路径 | 两边之间至少有两条不共点的路径 |
| 边双间由桥边连接 | 点双内没有割点 |
| 边双间由桥边连接 | 点双间由割点连接 |
另外，一个点双也是一个特殊的边双，就像一个点仙人掌是一个特殊的边仙人掌一样。
那就容易看出本题就是一个点双缩点的裸题了。把所有的割点和点双分量拿出来，让每一个割点向它所在的点双分量连边即可。可能把图“缩成树”这种事本来就适合边双干，点双写起来不是很自然，也没什么办法。
代码
#include<bits/stdc++.h>
#define FOR(i, x, y) for(int i = (x), i##END = (y); i <= i##END; ++i)
#define DOR(i, x, y) for(int i = (x), i##END = (y); i >= i##END; --i)
template<typename T, typename _T> inline bool chk_min(T &x, const _T &y) {return y < x ? x = y, 1 : 0;}
template<typename T, typename _T> inline bool chk_max(T &x, const _T &y) {return x < y ? x = y, 1 : 0;}
typedef long long ll;
const int N = 10005;
const int M = 100005;
template<const int N, const int M, typename T> struct Linked_List
{
int head[N], nxt[M], tot; T to[M];
Linked_List() {clear();}
T &operator [](const int x) {return to[x];}
void clear() {memset(head, -1, sizeof(head)), tot = 0;}
void add(int u, T v) {to[tot] = v, nxt[tot] = head[u], head[u] = tot++;}
#define EOR(i, G, u) for(int i = G.head[u]; ~i; i = G.nxt[i])
};
Linked_List<N, M << 1, int> G;
Linked_List<N << 1, N << 2, int> T;
int dfn[N], low[N], stk[M], bel[M], dfn_idx, bcc, tp, tot;
bool mark[M];
int fa[N << 1], dep[N << 1], sz[N << 1], son[N << 1], top[N << 1];
int n, m, q;
void tarjan(int u, int fa_e)
{
dfn[u] = low[u] = ++dfn_idx;
EOR(i, G, u)
{
if(i == (fa_e ^ 1)) continue;
int v = G[i];
if(!dfn[v])
{
stk[++tp] = i;
tarjan(v, i), chk_min(low[u], low[v]);
if(low[v] >= dfn[u])
{
bcc++;
do bel[stk[tp] / 2] = bcc;
while(stk[tp--] != i);
}
}
else if(dfn[v] < dfn[u])
{
stk[++tp] = i;
chk_min(low[u], dfn[v]);
}
}
}
void dfs(int u, int f, int d)
{
fa[u] = f, dep[u] = d, sz[u] = 1, son[u] = 0;
EOR(i, T, u)
{
int v = T[i];
if(v == f) continue;
dfs(v, u, d + 1);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
void hld(int u, int tp)
{
top[u] = tp;
if(son[u]) hld(son[u], tp);
EOR(i, T, u)
{
int v = T[i];
if(v == fa[u] || v == son[u]) continue;
hld(v, v);
}
}
int get_lca(int u, int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
int get_dis(int u, int v)
{
int lca = get_lca(u, v);
return dep[u] + dep[v] - 2 * dep[lca];
}
int main()
{
while(scanf("%d%d", &n, &m), (n || m))
{
G.tot = T.tot = 0;
FOR(i, 1, n) G.head[i] = -1, dfn[i] = 0;
FOR(i, 1, 2 * n) T.head[i] = -1, dep[i] = 0;
bcc = dfn_idx = tp = 0;
FOR(i, 1, m)
{
int u, v;
scanf("%d%d", &u, &v);
G.add(u, v), G.add(v, u);
}
FOR(i, 1, n) if(!dfn[i]) tarjan(i, -1);
tot = bcc;
FOR(u, 1, n)
{
tp = 0;
EOR(i, G, u)
{
if(!mark[bel[i / 2]])
{
mark[bel[i / 2]] = 1;
stk[++tp] = bel[i / 2];
}
}
if(tp >= 2)
{
tot++;
FOR(i, 1, tp) T.add(tot, stk[i]), T.add(stk[i], tot);
}
while(tp) mark[stk[tp]] = 0, tp--;
}
FOR(i, 1, tot) if(!dep[i]) dfs(i, 0, 1), hld(i, i);
scanf("%d", &q);
while(q--)
{
int e1, e2;
scanf("%d%d", &e1, &e2);
e1--, e2--;
printf("%d
", get_dis(bel[e1], bel[e2]) / 2);
}
}
return 0;
}