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++ ,

上一个：内存管理、野指针、读写字符的函数、预编译处理、宏定义及条件编译的知识总结
下一个：前置和后置运算符