首页 > 代码库 > POJ 1330 LCA最近公共祖先 离线tarjan算法

POJ 1330 LCA最近公共祖先 离线tarjan算法

2024-07-16 18:34:44   223人阅读

题意要求一棵树上，两个点的最近公共祖先 即LCA

现学了一下LCA-Tarjan算法，还挺好理解的，这是个离线的算法，先把询问存贮起来，在一遍dfs过程中，找到了对应的询问点，即可输出

原理用了并查集和dfs染色，先dfs到底层开始往上回溯，边并查集合并 一边染色，这样只要询问的两个点均被染色了，就可以输出当前并查集的最高父亲一定是LCA，因为我是从底层层层往上DSU和染色的，要么没被染色，被染色之后，肯定就是当前节点是最近的

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int N = 10000+10;int f[N],pre[N],vis[N];int ans[N];vector<int> v[N];int n,S,T;void init(){    for (int i=0;i<=n+1;i++){        f[i]=i;        v[i].clear();        vis[i]=0;        pre[i]=-1;    }}int findset(int x){    if (x!=f[x]){        f[x]=findset(f[x]);    }    return f[x];}int unionset(int a,int b){    int r1=findset(a);    int r2=findset(b);    if (r1==r2) return r1;    f[r2]=r1;    return r1;}void LCA(int u){    ans[u]=u;    for (int i=0;i<v[u].size();i++){        int vx=v[u][i];        LCA(vx);        int rt=unionset(u,vx);        ans[rt]=u;    }    vis[u]=1;    if (u==S){        if (vis[T]){            printf("%d\n",ans[findset(T)]);            return;        }    }    else    if (u==T){        if (vis[S]){            printf("%d\n",ans[findset(S)]);            return;        }    }}int main(){    int t,a,b;    scanf("%d",&t);    while (t--){      scanf("%d",&n);      init();      for (int i=1;i<n;i++){          scanf("%d%d",&a,&b);          v[a].push_back(b);          pre[b]=a;      }      scanf("%d%d",&S,&T);      for (int i=1;i<=n;i++){          if (pre[i]==-1){              LCA(i);              break;          }      }    }    return 0;}

　　


联系
我们