洛谷P10953 逃不掉的路 题解 边双连通分量（缩点）+ LCA

题目链接：https://www.luogu.com.cn/problem/P10953

解题思路：

缩点之后是棵树，答案是两点对应的的点在树上的距离。

因为缩点之后的树上的每一条边都对应一座桥。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;int n, m, q, ts, dcc, dfn[maxn], low[maxn], bl[maxn], fa[maxn][17], dep[maxn];
vector<int> g[maxn], G[maxn];
stack<int> stk;void tarjan(int u, int p) {dfn[u] = low[u] = ++ts;stk.push(u);for (auto v : g[u]) {if (v == p)continue;if (!dfn[v])tarjan(v, u), low[u] = min(low[u], low[v]);elselow[u] = min(low[u], dfn[v]);}if (low[u] == dfn[u]) {dcc++;int v;do {v = stk.top();stk.pop();bl[v] = dcc;} while (u != v);}
}void dfs(int u, int p, int d) {fa[u][0] = p;dep[u] = d;for (auto v : G[u])if (v != p)dfs(v, u, d+1);
}int lca(int x, int y) {if (dep[x] < dep[y])swap(x, y);for (int i = 16; i >= 0; i--) {if (dep[x] - dep[y] >= (1<<i))x = fa[x][i];}if (x == y) return x;for (int i = 16; i>= 0; i--) {if (fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];}return fa[x][0];
}int dis(int x, int y) {int z = lca(x, y);return dep[x] + dep[y] - 2 * dep[z];
}int main() {scanf("%d%d", &n, &m);for (int i = 0, u, v; i < m; i++) {scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}tarjan(1, -1);for (int u = 1; u <= n; u++) {for (auto v : g[u]) {int x = bl[u], y = bl[v];if (x != y) {G[x].push_back(y);}}}dfs(1, 0, 0);for (int j = 1; j <= 16; j++)for (int i = 1; i <= dcc; i++)fa[i][j] = fa[ fa[i][j-1] ][j-1];scanf("%d", &q);for (int i = 0, a, b; i < q; i++) {scanf("%d%d", &a, &b);printf("%d\n", dis(bl[a], bl[b]));}return 0;
}