POJ 1330 -- Nearest Common Ancestors

1330 -- Nearest Common Ancestors

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:


In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.

Write a program that finds the nearest common ancestor of two distinct nodes in a tree.

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.

Output

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.

http://blog.csdn.net/cxllyg/article/details/7635992

1. int f[MAX];//每个节点所属集合  
2. int r[MAX];//r是rank（秩）合并  
3. int indegree[MAX];//保存每个节点的入度  
4. int visit[MAX];//只有0和1，表示节点是否已处理完毕  
5. vector<int> tree[MAX], Qes[MAX];//数，待查询的节点组合  
6. int ancestor[MAX];//祖先集合  
7.   
8. void init(int n)//初始化  
9. {  
10.     for(int i=1; i<=n; i++)  
11.     {  
12.         r[i]=1;//初始秩为1  
13.         f[i]=i;//每个节点的父节点初始为自身  
14.         indegree[i]=0;  
15.         visit[i]=0;  
16.         ancestor[i]=0;  
17.         tree[i].clear();  
18.         Qes[i].clear();  
19.     }  
20. }  
21.   
22. int find(int n)//查找n所在集合，并压缩路径  
23. {  
24.     if(f[n]==n)  
25.         return n;  
26.     else  
27.         f[n]=find(f[n]);  
28.     return f[n];  
29. }  
30.   
31. int Union(int x, int y)//合并函数，若属于同一分支则返回0，成功合并返回1  
32. {  
33.     int a=find(x);  
34.     int b=find(y);  
35.     if(a==b)  
36.         return 0;  
37.     else if(r[a]<r[b])  
38.     {  
39.         f[a]=b;  
40.         r[b]+=r[a];  
41.     }  
42.     else  
43.     {  
44.         f[b]=a;  
45.         r[a]+=r[b];  
46.     }  
47.     return 1;  
48. }  
49.   
50. void LCA(int u)//tarjan求最近公共祖先  
51. {  
52.     ancestor[u]=u;  
53.     int size=tree[u].size();  
54.     //一个一个子节点处理  
55.     for(int i=0; i<size; i++)  
56.     {  
57.         LCA(tree[u][i]);  
58.         Union(u, tree[u][i]);  
59.         ancestor[find(u)]=u;  
60.     }  
61.   
62.     //处理完子节点，置visit[u]=1  
63.     visit[u]=1;  
64.   
65.     //求当前节点与有关的节点的最近公共祖先  
66.     size=Qes[u].size();  
67.     for(i=0; i<size; i++)  
68.     {  
69.         if(visit[Qes[u][i]]==1)//如果这个节点已处理过  
70.         {  
71.             cout<<ancestor[find(Qes[u][i])]<<endl;  
72.             continue;  
73.         }  
74.     }  
75. }  
76.   
77. int main()  
78. {  
79.     int n=16;//树的总节点  
80.     init(n);  
81.     int s, t;  
82.   
83.     //构造树    
84.     //输入要查询最近公共祖先的两个节点  
85.     cin>>s>>t;  
86.   
87.     //如果s在t左边，那么在遍历完s时还不能求得LCA，所以这里相当于访问两次，在访问t时即可求得结果  
88.     Qes[s].push_back(t);  
89.     Qes[t].push_back(s);  
90.   
91.     for(int i=1; i<=n; i++)  
92.     {  
93.         //寻找根节点  
94.         if(indegree[i]==0)//根节点的入度为0  
95.         {  
96.             LCA(i);  
97.             break;  
98.         }  
99.     }  

Read full article from 1330 -- Nearest Common Ancestors