正題

題目鏈接：
http://poj.org/problem?id=1330

---

題目大意

就是給出一棵樹(shù)，求LCA（最近公共祖先）

---

解題思路

用tarjan求LCA，這里給出tarjan算法

---

代碼

#include<cstdio> #include<iostream> using namespace std; struct line{int next,to; }a[20001]; int father[10001],n,m,q,p,v[10001],ans,tot,ls[10001],t,x,y,in[10001]; bool ok; void addl(int x,int y)//加邊 {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } int find(int x)//并查集優(yōu)化 {return x==father[x]?x:find(father[x]); } void tarjan(int x) {v[x]=1;for (int i=ls[x];i;i=a[i].next)//子節(jié)點(diǎn){int y=a[i].to;if (v[y]) continue;tarjan(y);//tarjan一遍father[y]=x;//記錄祖先}if (ok) return;//標(biāo)記已找到if (v[q]==2 && x==p){printf("%d\n",find(q));//輸出ok=true;return;}if (v[p]==2 && x==q)///輸出{printf("%d\n",find(p));ok=true;return;}v[x]=2; } int main() {scanf("%d",&t);for (;t;t--){scanf("%d",&n);tot=0;ok=0;for (int i=1;i<=n;i++){ls[i]=0;father[i]=i;v[i]=0;in[i]=0;}for (int i=1;i<n;i++){scanf("%d%d",&x,&y);in[y]++;addl(x,y);addl(y,x);}scanf("%d%d",&q,&p);for (int i=1;i<=n;i++)//尋找根if (in[i]==0) tarjan(i);//printf("%d\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的POJ1330-Nearest Common Ancestors【tarjan,LCA】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。