可能是除了《概率论》的最水的黑题了吧 用
\(Tarjan\)缩点（点双联通分量），然后就是树上两点之间的距离了，跑
\(LCA\)就好了。
#include #include #include using namespace std;int s; char ch;inline int read(){ s = 0; ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s;}const int MAXN = 10010;const int MAXM = 50010;int dfn[MAXN], low[MAXN], id, bridge[MAXM << 1], dcc, belong[MAXN], top, vis[MAXN];int n, m, a, b, head[MAXN], num = 1, f[MAXN][20], dep[MAXN], t, stack[MAXN];struct Edge{ int from, next, to;}e[MAXM << 2];inline void Add(int from, int to){ e[++num].to = to; e[num].from = from; e[num].next = head[from]; head[from] = num; e[++num].to = from; e[num].from = to; e[num].next = head[to]; head[to] = num;}void Tarjan(int u, int fa){ dfn[u] = low[u] = ++id; stack[++top] = u; vis[u] = 1; for(int i = head[u]; i; i = e[i].next) if(e[i].to != fa) if(!dfn[e[i].to]){ Tarjan(e[i].to, u); low[u] = min(low[u], low[e[i].to]); } else if(vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]); if(dfn[u] == low[u]){ ++dcc; do belong[stack[top]] = dcc; while(stack[top--] != u); }}void getDF(int u, int fa){ f[u][0] = fa; dep[u] = dep[fa] + 1; for(int i = head[u]; i; i = e[i].next) if(e[i].to != fa) getDF(e[i].to, u);}int LCA(int u, int v){ if(dep[u] < dep[v]) swap(u, v); int cha = dep[u] - dep[v]; if(cha) for(int i = 0; i <= 18; ++i) if((cha >> i) & 1) u = f[u][i]; if(u != v){ for(int i = 18; ~i; --i) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i]; return f[u][0]; } return u;}int dis(int u, int v){ return dep[u] + dep[v] - (dep[LCA(u, v)] << 1) + 1;}void print(int x){ if(x > 1) print(x >> 1); printf("%d", x & 1);}int main(){ n = read(); m = read(); for(int i = 1; i <= m; ++i) Add(read(), read()); for(int i = 1; i <= n; ++i) if(!dfn[i]) Tarjan(i, 0); memset(head, 0, sizeof head); int tmp = num; for(int i = 2; i <= tmp; i += 2) if(belong[e[i].from] != belong[e[i].to]) Add(belong[e[i].from], belong[e[i].to]); getDF(1, 0); for(int j = 1; j <= 18; ++j) for(int i = 1; i <= dcc; ++i) f[i][j] = f[f[i][j - 1]][j - 1]; t = read(); while(t--) print(dis(belong[read()], belong[read()])), puts(""); return 0;}