首页 > 代码库 > poj 1330 Nearest Common Ancestors （最简单的LCA）
poj 1330 Nearest Common Ancestors （最简单的LCA）
题意：
给出一棵树的结构。
给出两个点X和Y，求它俩的LCA。
思路：
只需求两个点的LCA，用了两种方法，一种离线tarjan，一种直接搞。
看代码。
代码：
方法一：直接搞。
int const maxn = 10005;int T,n,a,b;int fa[maxn];int X,Y;int main(){ cin>>T; while(T--){ scanf("%d",&n); mem(fa,-1); rep(i,1,n-1){ scanf("%d%d",&a,&b); fa[b]=a; } scanf("%d%d",&X,&Y); map<int,char> mp; int t1=X; while(t1!=-1){ mp[t1]=1; t1=fa[t1]; } t1=Y; while(t1!=-1){ if(mp[t1]==1){ printf("%d\n",t1); break; } t1=fa[t1]; } }}
方法二：离线tarjan。
int const maxn = 10005;struct node{ int to,w,next,lca;};node edge[maxn*2];bool vis[maxn];int cnt1,cnt2;int head[maxn], fa[maxn];bool flag;int X,Y,n;inline void Addedge(int u,int v,int w){ edge[++cnt1].w=w; edge[cnt1].to=v; edge[cnt1].next=head[u]; head[u]=cnt1;}void init(){ mem(head,-1); mem(vis,false); cnt1=0; flag=false; rep(i,1,n) fa[i]=i;}int findFa(int x){ if(fa[x]==x) return fa[x]; return fa[x]=findFa(fa[x]);}void Tarjan_LCA(int u){ //离线LCA算法 if(flag) return; fa[u]=u; vis[u]=true; for(int i=head[u];i!=-1;i=edge[i].next){ if(!vis[edge[i].to]){ Tarjan_LCA(edge[i].to); fa[edge[i].to]=u; } } if(u==Y && !flag){ if(vis[X]){ printf("%d\n",findFa(X)); flag=true; return; } } if(u==X && !flag){ if(vis[Y]){ printf("%d\n",findFa(Y)); flag=true; return; } }}int T,a,b;int main(){ cin>>T; while(T--){ scanf("%d",&n); init(); bool t1[maxn]={0}; rep(i,1,n-1){ scanf("%d%d",&a,&b); Addedge(a,b,1); t1[b]=true; } scanf("%d%d",&X,&Y); rep(i,1,n) if(!t1[i]){ Tarjan_LCA(i); //i为树的根结点 break; } }}
poj 1330 Nearest Common Ancestors （最简单的LCA）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。