题解：P10953 逃不掉的路

zlqwq · 2024-12-11 20:55:59 · 题解

一道非常难的板子题。

如果直接在原图上求答案显然很复杂，故可以用 Tarjan 来求出所有的边双连通分量，这样我们就可以在树上利用 lca 求解答案了。

我们发现，当我们在两个连通分量里求答案时，它们之间的边一定要统计，故先 Tarjan，然后求出它们树上的 lca 即可。

代码：

#include<iostream>
#include<vector>
#include<stack>
#include<cmath> 
using namespace std;
const int MAXN=1e5+5;
const int MAXM=2e5+5;
vector<int> z[MAXN];
int u[MAXM],v[MAXM];
int idx,IDX=1,belong[MAXN],c;
int n,m,dfn[MAXN],low[MAXN];
int to[MAXM*4],nxt[MAXM*4],head[MAXM];
int dep[MAXN];
int f[MAXN][21];
stack<int> s; 
void add(int u,int v){
    to[++IDX]=v;
    nxt[IDX]=head[u];
    head[u]=IDX;
}
void tarjan(int u,int lst){
    dfn[u]=low[u]=++idx;
    s.push(u);
    for(int i=head[u];i;i=nxt[i]){
        if(!dfn[to[i]]){
            tarjan(to[i],i);
            low[u]=min(low[to[i]],low[u]);
        }
        else if(i^(lst^1)){
            low[u]=min(low[u],dfn[to[i]]);
        }
    }
    if(dfn[u]==low[u]){
        belong[u]=++c;
        while(s.top()!=u){
            belong[s.top()]=c;
            s.pop();
        }
        s.pop();
    }
}
void init(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=20;++i){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(auto v:z[u]){
        if(v^fa){
            init(v,u);
        }
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v]){
        swap(u,v);
    }
    for(int k=20;k>=0;--k){
        if(dep[f[u][k]]>=dep[v]){
            u=f[u][k];
        }
    }
    if(u==v){
        return u;
    }
    for(int k=20;k>=0;--k){
        if(f[u][k]!=f[v][k]){
            u=f[u][k];
            v=f[v][k];
        }
    }
    return f[u][0];
}
int Q;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>u[i]>>v[i];
        add(u[i],v[i]);
        add(v[i],u[i]);
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i]){
            tarjan(i,0);
        }
    }
    for(int i=1;i<=m;++i){
        if(belong[u[i]]^belong[v[i]]){
            z[belong[u[i]]].push_back(belong[v[i]]);
            z[belong[v[i]]].push_back(belong[u[i]]);
        }
    }
    init(1,0);
    cin>>Q;
    while(Q--){
        int u,v;
        cin>>u>>v;
        int LCA=lca(belong[u],belong[v]);
        cout<<dep[belong[u]]+dep[belong[v]]-dep[LCA]-dep[LCA]<<'\n';
    }
    return 0;
}