Nearest Common Ancestors
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 18136 | Accepted: 9608 |
Description
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
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
Sample Input
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
Sample Output
4
3
Source
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std; const int LEN = ; vector<int> vec[LEN];
int uset[LEN];
bool vis[LEN];
bool root[LEN]; void init(int n)
{
for(int i = ; i <= n; i++)
vec[i].clear();
} void makeset(int n)
{
uset[n] = n;
} int findset(int x)
{
return x == uset[x] ? x : uset[x] = findset(uset[x]);
} void unionset(int x, int y) //并查集操作
{
x = findset(x);
y = findset(y);
if (x == y)
return;
uset[y] = x;
} void LCA(int u, int q1, int q2)
{
int v;
makeset(u);
for(int i = ; i < vec[u].size(); i++){
v = vec[u][i];
LCA(v, q1, q2);
unionset(u, v); //后续遍历并合并集合
}
vis[u] = true;
if (u == q1 && vis[q2] == true){ //如果访问到询问点，判断另外一个点是否被访问过，如果访问过则该点为最近公共祖先
printf("%d\n", findset(q2));
return;
}
else if (u == q2 && vis[q1] == true){
printf("%d\n", findset(q1));
return;
} } int main()
{
int T, n, a, b, q1, q2;
scanf("%d", &T);
while(T--){
memset(uset, , sizeof(uset));
memset(vis, , sizeof(vis));
memset(root, , sizeof(root));
scanf("%d", &n);
init(n);
for(int i = ; i < n - ; i++){
scanf("%d %d", &a, &b);
vec[a].push_back(b);
root[b] = true; //标注非根节点
}
scanf("%d %d", &q1, &q2);
for(int i = ; i <= n; i++)
if (root[i] != true){ //从根节点开始遍历
LCA(i, q1, q2);
break;
}
}
return ;
}