POJ_1330 Nearest Common Ancestors

本文主要是介绍POJ_1330 Nearest Common Ancestors，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

　　求一棵树上的某两个节点的最近公共祖先。

思路

　　这是tarjan算法的例题，所以我这里用的是tarjan算法。

代码

#include<cstdio>
#include<cstring>
using namespace std;
int f1,f2,p,q,t,n,m,x,y,root,tot,head[10001],v[10001],fa[10001];
struct node{int x,y,next;
}edge[10001];
int find(int x)
{return x==fa[x]?x:fa[x]=find(fa[x]);
}
void insert(int x,int y)
{f1=find(x);f2=find(y);if (f1!=f2) fa[f1]=f2;
}
void dfs(int x)
{v[x]=1;if (x==p&&v[q]||x==q&&v[p])//如果两个点都搜过了那我们就能得出答案if (x==p) printf("%d\n",find(q));else printf("%d\n",find(p));for (int i=head[x];i;i=edge[i].next)//继续遍历{dfs(edge[i].y);insert(edge[i].y,x);//合并并查集}
}
int main()
{scanf("%d",&t);for (int i=1;i<=t;i++){scanf("%d",&n);memset(head,0,sizeof(head));memset(v,0,sizeof(v));for (int i=1;i<n;i++)//建邻接表{scanf("%d%d",&edge[i].x,&edge[i].y);edge[i].next=head[edge[i].x];head[edge[i].x]=i;v[edge[i].y]=1;}scanf("%d%d",&p,&q);for (int i=1;i<=n;i++)if (v[i]==0) {root=i;break;}//找到入度为0的节点作为根去寻找   for (int i=1;i<=n;i++)fa[i]=i;//并查集的初始化memset(v,0,sizeof(v));dfs(root);//从root开始搜索}
}

这篇关于POJ_1330 Nearest Common Ancestors的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---