首页 > 代码库 > POJ 1330:Nearest Common Ancestors【lca】
POJ 1330:Nearest Common Ancestors【lca】
题目大意:唔 就是给你一棵树 和两个点,问你这两个点的LCA是什么
思路:LCA的模板题,要注意的是在并查集合并的时候并不是随意的,而是把叶子节点合到父节点上
#include<cstdio>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define maxn 10002
#define MOD 1000000007
using namespace std;
int head[maxn],point[maxn],next[maxn],father[maxn];
int now=0,in[maxn],finish=0;
bool visit[maxn];
inline int read()
{
int x=0;char ch=getchar();
while(ch<‘0‘||ch>‘9‘)ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x;
}
void add(int x,int y)
{
next[++now]=head[x];
head[x]=now;
point[now]=y;
}
int find(int x)
{
if(x==father[x])return x;
return father[x]=find(father[x]);
}
void dfs(int k,int s,int t)
{
for(int i=head[k];i;i=next[i])
{
if(finish==1)return;
int u=point[i];
dfs(u,s,t);
int x=find(k),y=find(u);
if(x!=y)father[y]=x;
}
visit[k]=1;
if(k==s && visit[t]){printf("%d\n",find(t));finish=1;}
else if(k==t && visit[s]){printf("%d\n",find(s));finish=1;}
return ;
}
int main()
{
int tt,n,x,y,root,s,t;
scanf("%d",&tt);
while(tt--)
{
now=finish=0;
n=read();
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<n;i++)
{
x=read(),y=read();
add(x,y);
in[y]++;
}
for(int i=1;i<=n;i++)if(in[i]==0)root=i;else in[i]=0;
s=read(),t=read();
dfs(root,s,t);
int u=sizeof(int)*(n+3);
int v=sizeof(bool)*(n+3);
memset(visit,0,v);
memset(head,0,u);
}
return 0;
}
POJ 1330:Nearest Common Ancestors【lca】