poj1330 Nearest Common Ancestors
时间复杂度分析:找父节点集合O(n),排序O(nlogn),二分O(logn),二分次数不超过n/2次,因此算法复杂度是O(nlogn)
代码:
[cpp]
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int p[10008],pa[10008],pb[10008];
void getFa(int x,int &n,int *f){
n=0;
f[n++]=x;
while(p[x]){//直到找到根节点,p[x]=0表x为树根
x=p[x];
f[n++]=x;
}
}
//二分搜索
int binarySearch(int e,int *a,int n){
int l=0,h=n-1,mid;
while(l<=h){
mid=(l+h)/2;
if(a[mid]==e)return e;
if(a[mid]>e) h=mid-1;
else l=mid+1;
}
return -1;
}
//找最近共同祖先
int findMCA(int a,int b,int na,int nb){
if(a==b) return a;
if(na>nb){//b可能是a祖先,所以用b的祖先“由近及远”地判断是否为a的祖先,下同
sort(pa,pa+na);
for(int i=0;i<nb;i++){
int tmp=binarySearch(pb[i],pa,na);
if(tmp!=-1)return tmp;
}
}
else{
sort(pb,pb+nb);
for(int i=0;i<na;i++){
int tmp=binarySearch(pa[i],pb,nb);
if(tmp!=-1)return tmp;
}
}
}
int main(){
int n,t,pat,son;
int a,b,na,nb;
cin>>t;
while(t--){
cin>>n;
memset(p+1,0,sizeof(int)*n);
for(int i=1;i<n;i++){
cin>>pat>>son;
p[son]=pat;
}
cin>>a>>b;
//分别记录a,b的所有祖先
getFa(a,na,pa);
getFa(b,nb,pb);
//找出最近共同祖先
cout<<findMCA(a,b,na,nb)<<endl;
}
return 0;
}
补充:软件开发 , C++ ,