按照vdcc缩点之后一条边只会属于一个新的点集，由于这棵树上满足（不是割点） - （割点） - （不是割点）的连接方法，所以求两条边之间的必经点就是（树上距离 / 2），倍增跳lca即可
考虑到缩点后树上点数的编号可能超过n，所以与树有关的数组开两倍N 又是一个模板Code：
#include#include #include using namespace std;const int N = 1e4 + 5;const int M = 1e5 + 5;const int Lg = 25;int n, m, qn, tot, head[2][N << 1], top, sta[N];int dfsc, dfn[N], low[N], dccCnt, root;int bel[N], eb[M], fa[N << 1][Lg], dep[N << 1], id[N];bool cut[N], vis[N << 1];vector dcc[N];struct Edge { int to, nxt, id;} e[M << 2];inline void add(int type, int from, int to, int eid) { e[++tot].to = to; e[tot].id = eid; e[tot].nxt = head[type][from]; head[type][from] = tot;}inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op;}inline int min(int x, int y) { return x > y ? y : x;}void tarjan(int x) { dfn[x] = low[x] = ++dfsc; sta[++top] = x; if(x == root && head[0][x] == 0) { dcc[++dccCnt].push_back(x); return; } int son = 0; for(int i = head[0][x]; i; i = e[i].nxt) { int y = e[i].to; if(!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); if(dfn[x] <= low[y]) { ++son; if(x != root || son > 1) cut[x] = 1; ++dccCnt; for(int z; ; ) { z = sta[top--]; dcc[dccCnt].push_back(z); if(z == y) break; } dcc[dccCnt].push_back(x); } } else low[x] = min(low[x], dfn[y]); }}void dfs(int x, int fat, int depth) { vis[x] = 1, fa[x][0] = fat, dep[x] = depth; for(int i = 1; i <= 15; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1]; for(int i = head[1][x]; i; i = e[i].nxt) { int y = e[i].to; if(vis[y]) continue; dfs(y, x, depth + 1); }}inline void swap(int &x, int &y) { int t = x; x = y; y = t;}inline int getLca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); for(int i = 15; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i]; if(x == y) return x; for(int i = 15; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0];}int main() { for(; ; ) { read(n), read(m); if(n == 0 && m == 0) break; tot = 0; memset(head, 0, sizeof(head)); for(int x, y, i = 1; i <= m; i++) { read(x), read(y); add(0, x, y, i), add(0, y, x, i); } dfsc = dccCnt = top = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(cut, 0, sizeof(cut)); for(int i = 1; i <= n; i++) dcc[i].clear(); for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(root = i); int now = dccCnt; for(int i = 1; i <= n; i++) if(cut[i]) id[i] = ++now; /* printf("\n"); for(int i = 1; i <= dccCnt; i++, printf("\n")) { for(unsigned int j = 0; j < dcc[i].size(); j++) printf("%d ", dcc[i][j]); } printf("\n"); */ for(int i = 1; i <= dccCnt; i++) { for(unsigned int j = 0; j < dcc[i].size(); j++) { int x = dcc[i][j]; if(cut[x]) add(1, id[x], i, 0), add(1, i, id[x], 0); bel[x] = i; } for(unsigned int j = 0; j < dcc[i].size(); j++) { int x = dcc[i][j]; for(int k = head[0][x]; k; k = e[k].nxt) { int y = e[k].to; if(bel[y] == i) eb[e[k].id] = i; } } } /* for(int i = 1; i <= n; i++) printf("%d ", bel[i]); printf("\n"); for(int i = 1; i <= m; i++) printf("%d ", eb[i]); printf("\n"); */ memset(dep, 0, sizeof(dep)); memset(fa, 0, sizeof(fa)); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= now; i++) if(!vis[i]) dfs(i, 0, 1); read(qn); for(int x, y; qn--; ) { read(x), read(y); x = eb[x], y = eb[y]; if(x == y) puts("0"); else printf("%d\n", (dep[x] + dep[y] - 2 * dep[getLca(x, y)]) / 2); } } return 0;}
lyd给的std好难看