P4320-道路相遇,P5058-[ZJOI2004]嗅探器【圓方樹,LCA】

兩題差不多就一起寫了

P4320-道路相遇

題目連結:https://www.luogu.com.cn/problem/P4320

題目大意

\(n\)個點\(m\)條邊的一張圖，\(q\)次詢問兩個點之間路徑的必經點數量。

解題思路

建出圓方樹然後問題就變為詢問兩個點之間路徑的圓點數量，可以直接倍增\(LCA\)求。當然還有更友善的，因為這兩個點是圓點，它們的路徑一定是一圓一方，是以答案就是它們直接的路徑長度\(len/2+1\)。也是倍增或者樹剖\(LCA\)就好了。

時間複雜度\(O(n\log n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=1e6+10,T=20;
int n,m,t,dfc,dfn[N],low[N];
int dep[N],f[N][T+1];
vector<int> G[N],H[N];
stack<int> s;
void tarjan(int x){
    dfn[x]=low[x]=++dfc;
    s.push(x);
    for(int y:G[x])
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]==dfn[x]){
                int k;++n;
                do{
                    k=s.top();s.pop();
                    H[n].push_back(k);
                    H[k].push_back(n);
                }while(k!=y);
                H[n].push_back(x);
                H[x].push_back(n);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    return;
}
void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    for(int y:H[x]){
        if(y==fa)continue;
        dfs(y,x);f[y][0]=x;
    }
    return;
}
int LCA(int x,int y){
    if(dep[x]>dep[y])swap(x,y);
    for(int i=T;i>=0;i--)
        if(dep[f[y][i]]>=dep[x])
            y=f[y][i];
    if(x==y)return x;
    for(int i=T;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    tarjan(1);dfs(1,0);
    for(int j=1;j<=T;j++)
        for(int i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
    scanf("%d",&t);
    while(t--){
        int x,y,p;
        scanf("%d%d",&x,&y);
        p=LCA(x,y);
        printf("%d\n",(dep[x]+dep[y]-2*dep[p])/2+1);
    }
    return 0;
}
           

P5058-[ZJOI2004]嗅探器

題目連結:https://www.luogu.com.cn/problem/P5058

一張\(n\)個點\(m\)條邊的無向圖，給出兩個點求它們之間編号最小的必經點。

一組詢問是以直接建好圓方樹\(dfs\)就好了，如果多組詢問的話也可以做，倍增維護樹鍊最小值就好了。

這題是一組詢問是以随便寫\(O(n)\)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=4e5+10;
int n,m,dfc,cnt,s,t,dfn[N],low[N];
vector<int> G[N],H[N];
stack<int> S;
void tarjan(int x){
    dfn[x]=low[x]=++dfc;
    S.push(x);
    for(int y:G[x])
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]==dfn[x]){
                int k;++cnt;
                do{
                    k=S.top();S.pop();
                    H[cnt].push_back(k);
                    H[k].push_back(cnt);
                }while(k!=y);
                H[cnt].push_back(x);
                H[x].push_back(cnt);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    return;
}
int dfs(int x,int fa){
    int k;
    if(x==t)return n+1;
    for(int y:H[x]){
        if(y==fa)continue;
        if(k=dfs(y,x))
            return min((x==s)?(n+1):x,k);
    }
    return 0;
}
int main()
{
    scanf("%d",&n);cnt=n;
    while(1){
        int x,y;
        scanf("%d%d",&x,&y);
        if(!x&&!y)break;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    scanf("%d%d",&s,&t);
    s=dfs(s,0);
    if(s>n||!s)printf("No solution\n");
    else printf("%d\n",s);
    return 0;
}