2
20
30
20

It doesn't have parent.

2
20
30
30

20

2个回答

`````` #include <iostream>

#include<stdio.h>

using namespace std;

const int size=10005;

int  T,N,first,second;

vectorvec[size];   //用来记录图的信息

bool root[size];              //用来查找根节点

int depth[size];               //用来记录该节点的深度

int father[size];               //用来记录该节点的父节点

//录入数据

void In_data()

{

scanf("%d",&N);

for(int i=1;i<=N;++i)

{

vec[i].clear();

depth[i]=0;

root[i]=true;

father[i]=i;

}

for(int i=1;i

{

int beg,end;

scanf("%d%d",&beg,&end);

vec[beg].push_back(end);

father[end]=beg;

root[end]=false;

}

scanf("%d%d",&first,&second);

}

//parent表示根节点，dep表示当前节点的深度

void depth_plus(int parent,int dep)

{

for(int i=0;i   {

depth_plus(vec[parent][i],dep+1);

}

depth[parent]=dep;

}

//在线算法查找最近公共祖先

int find_ancestor()

{

if(depth[first]>depth[second])

{

while(depth[first]!=depth[second])

{

first=father[first];

}

}

else if(depth[second]>depth[first])

{

while(depth[first]!=depth[second])

{

second=father[second];

}

}

while(first!=second)

{

first=father[first];

second=father[second];

}

return first;

}

int main()

{

//freopen("1.txt","r",stdin);

scanf("%d",&T);

while(T--)

{

In_data();

//以根节点为入口，给每个点赋予深度

for(int i=1;i<=N;++i)

{

if(root[i]==true)

{

depth_plus(i,0);

break;

}

}

printf("%d\n",find_ancestor());

}

}
``````
sinat_26083883 回复weixin_41107720: c你都看不懂

weixin_41107720 这是C++吗，我看不懂欸

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1005;
struct BinaryTree{
int val;
int l;
int r;
BinaryTree(){val=0;l=r=-1;}
}tree[N];
int ar[N],n,tot,x;
bool flag;//是否找到父节点
int ans;//答案
//递归建树，k为当前建树已经跑到了输入序列数组的第几号元素
void build(int k){
if(k>n)return;
tree[++tot].val=ar[k];
tree[tot].l=tree[tot].r=-1;
int i=1;
while(1){
if(ar[k]>=tree[i].val){//如果不小于此节点值就往右边建树
if(tree[i].r!=-1){
i=tree[i].r;
}else{
tree[i].r=tot;
break;
}
}else {
if(tree[i].l!=-1){
i=tree[i].l;
}else{
tree[i].l=tot;
break;
}
}
}
build(k+1);
return;
}
void Find(int k,int fa){
if(flag)return;//已找到就回溯
if(tree[k].val==x){
flag=true;
ans=fa;
return;
}
if(tree[k].l!=-1){//如果有左儿子往左搜索
Find(tree[k].l,tree[k].val);
if(flag)return;
}
if(tree[k].r!=-1){//如果有右儿子往右搜索
Find(tree[k].r,tree[k].val);
if(flag)return;
}
}
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;++i){
scanf("%d",&ar[i]);
}
tot=1;//节点编号
tree[1].val=ar[1];//根节点
tree[1].l=tree[1].r=-1;
build(2);
scanf("%d",&x);
flag=0;ans=-1;
Find(1,-1);//找x
if(flag==false||ans==-1)printf("It doesn't have parent.\n");
else printf("%d\n",ans );
}
return 0;
}
``````