本文主要是介绍poj 1330 Nearest Common Ancestors(LCA模板)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=1330
题意：给出两个点，求出这两个点最近的公共祖先。
求LCA的模板题。
大致思路就是访问到某个节点时，先将它自己加入集合中，然后递归访问它的子树，同时把子树加入到集合中来。子树搜索完毕后，判断该节点是否是输入的两个节点之一，若是，并且另外一个也已标记为访问过，那么另外一个节点的祖先便是他们的LCA。
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;const int maxn = 10010;
struct node
{int u,v,next;
}edge[maxn];int p[maxn],cnt;//前向星
int in[maxn];
int vis[maxn];
int pre[maxn];//祖先
int n,x,y;void add(int u, int v)//加边
{edge[cnt] = (struct node){u,v,p[u]};p[u] = cnt;cnt++;
}int find(int x)
{if(x != pre[x])pre[x] = find(pre[x]);return pre[x];
}void LCA(int u)
{pre[u] = u;//设立当前节点的集合，先把自己形成一个集合for(int i = p[u]; i != -1; i = edge[i].next){LCA(edge[i].v);//搜索子树pre[edge[i].v] = u;//合并子树}vis[u] = 1;//标记已被访问//如果当前点是查询中两点中的一点并且另外一点已经访问过，那么另一点的祖先即为公共祖先 if(u == x && vis[y]){printf("%d\n",find(y));return;}if(u == y && vis[x]){printf("%d\n",find(x));return;}
}int main()
{int test,u,v;scanf("%d",&test);while(test--){scanf("%d",&n);memset(p,-1,sizeof(p));memset(in,0,sizeof(in));memset(vis,0,sizeof(vis));cnt = 0;for(int i = 1; i < n; i++){scanf("%d %d",&u,&v);in[v]++;add(u,v);}scanf("%d %d",&x,&y);for(int i = 1; i <= n; i++){if(in[i] == 0)LCA(i);}}return 0;
}
这篇关于poj 1330 Nearest Common Ancestors(LCA模板)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
