poj1330——Nearest Common Ancestors
LCA离线算法，递归求解。详见：http://blogold.chinaunix.net/u3/105033/showart_2238641.html伪代码：
LCA(u)
{
Make-Set(u);
ancestor[Find-Set(u)]=u;
for every child v of u
{
LCA(v);
Union(u,v);
}
color=colored;
for every questioned pair (u,v)
{
if color==colored
{
the lca of (u,v) is ancestor[Find-Set(v)];
}
}
}
#include<iostream>#include<cstdio>using namespace std;int tree,in,p;int cas,s,t;int n,q1,q2;bool vis;void Make_Set(int t){p=t;}int Find(int t){if(t!=p)p=Find(p);return p;}void Union(int u,int v){p=u;}void LCA(int root){Make_Set(root);int i;for(i=1;i<=tree;i++){LCA(tree);Union(root,tree);}vis=1;if(root==q1&&vis)printf("%d\n",p);else if(root==q2&&vis)printf("%d\n",p);}int main(){scanf("%d",&cas);while(cas--){int i;memset(tree,0,sizeof(tree));memset(in,0,sizeof(in));memset(vis,0,sizeof(vis));scanf("%d",&n);for(i=1;i<n;i++){scanf("%d%d",&s,&t);tree[++tree]=t;in++;}scanf("%d%d",&q1,&q2);for(i=1;i<=n;i++){if(in==0) break;//根节点}LCA(i);}return 0;}
页:
[1]