程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj1330 Nearest Common Ancestors

poj1330 Nearest Common Ancestors

編輯:C++入門知識

時間復雜度分析:找父節點集合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;   }    

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved