题解：P10953 逃不掉的路

· · 题解

做题背景

做这题时机房里惨叫一片，大家不是 WA 就是 RE（其实我也一样）。

知识点

  1. 最近公共祖先（LCA），建议大家先做一下这道题：P3379 【模板】最近公共祖先（LCA）；
  2. 边双连通分量（edcc），建议大家做一下这道题：P8436 【模板】边双连通分量。

思路

通过画图发现，将原图进行缩点后会变成一棵树，而 u 点到 v 点的必经之路长度（几条路，也就是桥）就是 dep_u + dep_v - (dep_{lca_{u, v}} \times 2)。所以我们先跑一遍缩点，再遍历原始连边中的点，看看连边的点对是否在同一个连通分量里，如果不在，就将这两个点所在的缩点（连通分量）连边，再通过最近公共祖先求答案就好了。

代码

代码有些丑陋，不喜勿喷。

#include <bits/stdc++.h>
#define N 500005
#define M 20
using namespace std;
//typedef pair<int, int> PII;
int n, m, u, v, q, au[N], av[N], cnt1, EE = 1, cnt, dfn[N], low[N], dep[N], anc[N][M], edcc[N], pre[N];
vector<int> e[N];
//vector<vector<int> > ans;
stack<int> st;
struct node
{
    int to, ne;
} a[N];
void add(int u, int v) // 加边函数
{
    a[++EE] = (node){v, pre[u]};
    pre[u] = EE;
}
void tarjan(int u, int fa) // 缩点
{
    dfn[u] = low[u] = ++cnt;
    st.push(u);
    for (int i = pre[u]; i; i = a[i].ne)
    {
        int to = a[i].to;
        if (!dfn[to])
        {
            tarjan(to, i);
            low[u] = min(low[u], low[to]);
        }
        else if (i != (fa ^ 1))
            low[u] = min(low[u], dfn[to]);
    }
    if (dfn[u] == low[u])
    {
        edcc[u] = ++cnt1;
        while (st.top() != u)
        {
            edcc[st.top()] = cnt1;
            st.pop();
        }
        st.pop();
    }
}
void dfs(int u, int fa) // lca的初始化
{
    dep[u] = dep[fa] + 1;
    anc[u][0] = fa;
    for (int i = 1; i <= M - 2; i++)
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto uu : e[u])
    {
        int to = uu;
        if (to == fa)
            continue;
        dfs(to, u);
    }
}
//void init()
//{
//  for (int j = 1; j <= M - 1; j++)
//      for (int i = 1; i <= n; i++)
//          anc[i][j] = anc[anc[i][j - 1]][j - 1];
//}
int LCA(int x, int y) // 最近公共祖先（lca）
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = M - 3; ~i; i--)
        if (dep[anc[x][i]] >= dep[y])
            x = anc[x][i];
    if (x == y)
        return x;
    for (int i = M - 3; i >= 0; i--)
        if (anc[x][i] != anc[y][i])
            x = anc[x][i], y = anc[y][i];
    return anc[x][0];
}
int main()
{
    cin >> n >> m;
//  init();
    for (int i = 1; i <= m; i++)
    {
        cin >> au[i] >> av[i];
        add(au[i], av[i]);
        add(av[i], au[i]);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i, 0);
    for (int i = 1; i <= m; i++)
        if (edcc[au[i]] != edcc[av[i]])
            e[edcc[au[i]]].push_back(edcc[av[i]]), e[edcc[av[i]]].push_back(edcc[au[i]]);
    dfs(1, 0);
    cin >> q;
    while (q--)
    {
        cin >> u >> v;
        u = edcc[u], v = edcc[v];
        int lca = LCA(u, v);
        cout << dep[u] + dep[v] - (dep[lca] << 1) << endl;
    }
    return 0;
}
// 2025.1.25 16:12 build on FJQZ5Z

完结散花！