?? 求最近公共祖先.txt
字號:
#include <iostream>
#include <stdio.h>
using namespace std;
#define NMAX 10010
int zuxian[NMAX];
//求最近公共祖先
/*
輸入:
1
8
1 2
2 4
1 3
3 5
3 6
6 7
6 8
5 8
輸出:
3
*/
void init(int num)
{
int i;
for(i=1;i<=num;i++)
zuxian[i]=0;
}
int cal(int a,int b)
{
int aa[NMAX],bb[NMAX],i,t,numa,numb;
i=0;
t=a;
while(t!=0)
{
aa[i]=t;
t=zuxian[t];
i++;
}
numa=i;
i=0;
t=b;
while(t!=0)
{
bb[i]=t;
t=zuxian[t];
i++;
}
numb=i;
for(i=0;aa[numa-i-1]==bb[numb-i-1];i++);
return aa[numa-i];
}
int main()
{
int shijian,num,ta,tb;
scanf("%d",&shijian);
for(;shijian;shijian--)
{
scanf("%d",&num);
init(num);
for(;num-1;num--)
{
scanf("%d%d",&ta,&tb);
zuxian[tb]=ta;
}
scanf("%d%d",&ta,&tb);
cout<<cal(ta,tb)<<endl;
}
return 0;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -