poj----1330Nearest Common Ancestors（简单LCA)

 1 /*Source Code
 2 Problem: 1330        User: huifeidmeng
 3 Memory: 1232K        Time: 63MS
 4 Language: C++        Result: Accepted
 5 
 6     Source Code
 7 */
 8     #include<iostream>
 9     #include<vector>
10     #include<cstdio>
11     #include<cstring>
12     #include<cstdlib>
13     using namespace std;
14     const int maxn=10002;
15     vector<int> tree[maxn],qus[maxn];
16     int rank[maxn],father[maxn];
17     bool vis[maxn];
18     int rudu[maxn];
19     int lroot[maxn];
20     void init(int n){
21          memset(vis,0,sizeof(vis));
22          memset(rudu,0,sizeof(rudu));
23          memset(lroot,0,sizeof(lroot));
24         for(int i=1;i<=n;i++){
25             father[i]=i;
26             rank[i]=1;
27             tree[i].clear();
28             qus[i].clear();
29         }
30     }
31     int find(int a){
32        while(a!=father[a])
33              a=father[a];
34         return a;
35     }
36     void Union(int a,int b)
37     {
38         int x=find(a);
39         int y=find(b);
40         if(x==y) return ;
41         if(rank[x]<rank[y]){
42           rank[y]+=rank[x];
43           father[x]=y;
44         }
45         else {
46          rank[x]+=rank[y];
47          father[y]=x;
48         }
49     }
50     void LCA(int u)
51     {
52       lroot[u]=u;
53       int len=tree[u].size();
54       for(int i=0;i<len;i++){
55           LCA(tree[u][i]);
56           Union(u,tree[u][i]);
57           lroot[find(u)]=u;
58       }
59       vis[u]=1;
60       int ss=qus[u].size();
61       for(int i=0;i<ss;i++){
62             if(vis[qus[u][i]]){
63                 printf("%d\n",lroot[find(qus[u][i])]);
64                 return ;
65             }
66       }
67     }
68     int main()
69     {
70       int cas,n,u1,u2;
71       //freopen("test.in","r",stdin);
72       scanf("%d",&cas);
73       while(cas--){
74           scanf("%d",&n);
75           init(n);
76           for(int i=1;i<n;i++){
77           scanf("%d%d",&u1,&u2);
78           tree[u1].push_back(u2);
79           rudu[u2]++;  
80           }
81           scanf("%d%d",&u1,&u2);
82           qus[u1].push_back(u2);
83           qus[u2].push_back(u1);
84           for(int i=1;i<=n;i++){
85          if(0==rudu[i]){ //找到root
86            LCA(i);
87            break;
88           }
89           }
90       }
91     return 0;
92     }