【问题描述】

   如图所示是一棵有根树，图中每个结点用1～16的整数标识，结点8是树根。如果结点_x_位于根结点到结点_y_之间的路径中，则结点_x_是结点_y_的祖先。如果结点_x_是结点_y_和结点_z_的祖先，则结点_x_称为两个不同结点_y_和_z_的公共祖先。如果_x_是_y_和_z_的共同祖先并且在所有共同祖先中最接近_y_和_z_，则结点_x_被称为结点_y_和_z_的最近公共祖先，如果_y_是_z_的祖先，那么_y_和_z_的最近共同祖先是_y_。例如结点16和7的最近公共祖先是结点4，结点2和3的最近公共祖先是结点10，结点4和12的最近公共祖先是结点4。编写一个程序，找到树中两个不同结点的最近公共祖先。

image.png

【输入形式】

  每个测试用例的第一行为树中结点数_n_（2≤n_≤10,000），所有结点用整数1～_n_标识，接下来的_n-1行中的每一行包含一对表示边的整数，第一个整数是第二个整数的父结点。请注意，具有_n_个结点的树具有恰好_n_-1个边。每个测试用例的最后一行为两个不同整数，需要计算它们的最近公共祖先。

【输出形式】

   为每个测试用例输出一行，该行应包含最近公共祖先结点的编号。

【样例输入】

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

【样例输出】

4

【样例说明】

     测试数据的文件名为in.txt

【评分标准】

    该题目有10个测试用例，每通过一个测试用例，得10分。

思路

想法一 —— 并查集与双重循环

时间复杂度$O(n^2)$的笨方法

  1. 首先按照初始化的条件初始化并查集
  2. 对找所需寻找关系的两个结点，一个结点作为外层循环，一个结点放入内层循环，退出条件是两个结点的祖先相同，由于我们从所找结点向根节点的方向寻找，所以退出时找到的祖先结点就是最近祖先

想法二——大佬txl的指点

  1. 由于树中任意两结点之间的路径是唯一的，所以直接把所找结点到根节点的路径保存下来，在路径中找到最近公共祖先即可
  2. 如何寻找找到最近公共祖先，以下是两种$O(n)$的方法
    img.jpg
    1. 如果从当前节点先根节点移动的路径，则公共部分一定处在最后，所以如果两条路径长度相同，则设计两个指针指向两个，同步移动，每次移动后比较；如果长度不同，则需要长的那条指针先移动至两条路径长度相同再去比较（如（1））
    2. 逆向比较，则最后一个不同的就是最近公共祖先（如（2））当然如果使用递归寻找路径，路径本身就是（2）中的效果，本文采用（2）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<vector>
#include<fstream>
using namespace std;

vector<int> parent;
vector<int> rnk;

void Init(int n){
    for(int i = 0; i <= n; i++){
        parent.push_back(i);
        rnk.push_back(0);
    }
}

int FindAncestor1(int a, int b){
    int temp_for_a = a;
    bool flag = false;
    while (temp_for_a != parent[temp_for_a])
    {   
        int temp_for_b = b;
        while(parent[temp_for_b] != temp_for_b){
            if(parent[temp_for_b] == temp_for_a){
                flag = true;
                break;
            }
            temp_for_b = parent[temp_for_b];
        }
        if(flag){
            break;
        }
        temp_for_a = parent[temp_for_a];
    }
    return temp_for_a;
}

void FindPath(int x, vector<int>& path){
    if(parent[x] != x){
        FindPath(parent[x], path);
        path.push_back(x);
    }else{
        path.push_back(x);
    }
}

int FindAncestor2(vector<int> path1, vector<int> path2){
    int i = 0, j = 0;
    int path1_size = path1.size();
    int path2_size = path2.size();
    while(i < path1_size && j < path2_size){
        if(path1[i] == path2[j]){
            i++;
            j++;
        }else{
            break;
        }
    }
    return path1[i-1];
}

int main(){
    int n;
    ifstream file("in.txt");
    file >> n;
    Init(n);
    int num = n - 1;
    int a, b;
    //此循环用于构建结点间的关系
    while(num--){
        file >> a >> b;
        parent[b] = a;
    }
    //找到a、b的最近公共祖先
    file >> a >> b;
    vector<int> path1, path2;
    FindPath(a, path1);
    FindPath(b, path2);
    int ans = FindAncestor1(a, b);
    cout << ans << endl;
    int ans = FindAncestor2(path1, path2);
    cout << ans << endl;
    return 0;
}