【洛谷P4320】道路相遇 | Mrsrz's blog

缩点，圆方树

题目大意：

给定一张无向连通图，多次询问两个点之间所有路径的必经点个数。

题解：

缩点，建圆方树。

然后两点之间的圆点个数就是必经点个数。

对每个询问求 LCA 然后计算即可。

缩点部分时间复杂度 $O(n+m)$。

考前作为点双模板练习。CSP RP++

Code：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+6;
int n,m,head[N],cnt,dfn[N],low[N],idx,sta[N],top;
struct edge{
    int to,nxt;
}e[N<<1];
namespace tr{
    int n,head[N],cnt,tg[N],dep[N],dis[N],fa[N],sz[N],top[N],son[N];
    edge e[N<<1];
    inline void init(int n){
        tr::n=n;
        for(int i=1;i<=n;++i)tg[i]=1;
    }
    inline void addedge(int u,int v){
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    inline int newnode(){return ++n;}
    void dfs(int now){
        sz[now]=1;
        for(int i=head[now];i;i=e[i].nxt)
        if(!dep[e[i].to]){
            dep[e[i].to]=dep[now]+1,fa[e[i].to]=now;
            dis[e[i].to]=tg[e[i].to]+dis[now];
            dfs(e[i].to);
            sz[now]+=sz[e[i].to];
            if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
        }
    }
    void dfs2(int now){
        if(son[now])top[son[now]]=top[now],dfs2(son[now]);
        for(int i=head[now];i;i=e[i].nxt)
        if(e[i].to!=son[now]&&dep[e[i].to]>dep[now])
        dfs2(top[e[i].to]=e[i].to);
    }
    inline int LCA(int x,int y){
        while(top[x]!=top[y])
        if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
        return dep[x]<dep[y]?x:y;
    }
    void work(){
        dfs(dep[1]=dis[1]=1),dfs2(1);
        int q;
        cin>>q;
        while(q--){
            int u,v;
            cin>>u>>v;
            int w=LCA(u,v);
            cout<<dis[u]+dis[v]-2*dis[w]+tg[w]<<'\n';
        }
    }
}
void dfs(int now){
    sta[++top]=now;
    dfn[now]=low[now]=++idx;
    for(int i=head[now];i;i=e[i].nxt)
    if(!dfn[e[i].to]){
        dfs(e[i].to);
        low[now]=min(low[now],low[e[i].to]);
        if(low[e[i].to]>=dfn[now]){
            int id=tr::newnode();
            tr::addedge(now,id);
            int v;
            do{
                v=sta[top--];
                tr::addedge(v,id);
            }while(v!=e[i].to);
        }
    }else low[now]=min(low[now],dfn[e[i].to]);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(;m--;){
        int u,v;
        cin>>u>>v;
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    tr::init(n);
    for(int i=1;i<=n;++i)
    if(!dfn[i])dfs(i);
    tr::work();
    return 0;
}