洛谷 P3379 【模板】最近公共祖先（LCA）Tarjan离线

这道题目WA无数发，最后还是参考了大神的blog
谁会想到因为一个输入外挂WA呢
大概是我的挂是假挂吧...orz（其实加上外挂，速度提升很多）
用链式前向星保存边的关系，同时为了节省空间也用前向星保存询问
注意要双向建边，同时dfs是先标记为访问状态
否则，会因为双向边的问题陷入死循环，或者改变了深搜的方向

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500001;

const int maxm = 1000001;

struct enode {

    int next,to;

} edges[maxm];

struct qnode {

    int next,id,to;//id第几次查询

} que[maxm];

int head_e[maxn];//前向星 edges

int head_q[maxn];//前向星 查询

int vis[maxn];

int f[maxn];//并查集父亲数组

int res[maxn];//结果

int cnte=0;

int cntq=0;

int n,m,s;

inline void addedge(int u, int v) {

    edges[cnte].to=v;

    edges[cnte].next=head_e[u];

    head_e[u]=cnte++;

}

inline void addque(int u, int v, int id) {

    que[cntq].to=v;

    que[cntq].id=id;

    que[cntq].next=head_q[u];

    head_q[u]=cntq++;

}

//并查集访问父亲

int find(int x) {

    return x==f[x] ? x : f[x] = find(f[x]);//压缩

}

void tarjan(int s) {

    vis[s]=1;//先标记，不能在回溯时标记，因为双向边

    f[s]=s;

    for(int i=head_e[s]; i!=-1; i=edges[i].next) {

        if(!vis[edges[i].to]) {

            tarjan(edges[i].to);

            f[edges[i].to]=s;

        }

    }

    for(int i=head_q[s]; i!=-1; i=que[i].next) {

        if(vis[que[i].to]==1) {

            res[que[i].id]=find(que[i].to);

        }

    }

}

inline void init() {

    memset(vis,0,sizeof(vis));

    memset(head_e,-1,sizeof(head_e));

    memset(head_q,-1,sizeof(head_q));

    for(int i=1; i<=n; ++i) f[i]=i;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    cin>>n>>m>>s;

    init();

    int u,v;

    for(int i=1; i<n; ++i) {

        cin>>v>>u;

        addedge(v,u);

        addedge(u,v);

    }

    for(int i=1; i<=m; ++i) {

        cin>>v>>u;

        addque(u,v,i);

        addque(v,u,i);

    }

    tarjan(s);

    for(int i=1; i<=m; ++i) cout<<res[i]<<endl;

    return 0;

}

巴特西

洛谷 P3379 【模板】最近公共祖先（LCA）Tarjan离线

最新文章

热门文章