題意要求一棵樹上，兩個點的最近公共祖先 即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;}}elseif (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; }

　　

轉載于:https://www.cnblogs.com/kkrisen/p/3902868.html

總結

以上是生活随笔為你收集整理的POJ 1330 LCA最近公共祖先 离线tarjan算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。