求树中两个结点的最近公共祖先（LCA）算法详解

求树中两个结点的最近公共祖先（LCA）算法详解

问题描述

如图所示是一棵有根树，图中每个结点用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。编写一个程序，找到树中两个不同结点的最近公共祖先。

输入输出格式

• 输入格式：

• 每个测试用例的第一行为树中结点数_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. 对找所需寻找关系的两个结点，一个结点作为外层循环，一个结点放入内层循环，退出条件是两个结点的祖先相同，由于我们从所找结点向根节点的方向寻找，所以退出时找到的祖先结点就是最近祖先

方法二：保存路径寻找最近公共祖先

1. 由于树中任意两结点之间的路径是唯一的，所以直接把所找结点到根节点的路径保存下来，在路径中找到最近公共祖先即可
2. 如何寻找找到最近公共祖先，以下是两种$O(n)$的方法

1. 如果从当前节点先根节点移动的路径，则公共部分一定处在最后，所以如果两条路径长度相同，则设计两个指针指向两个，同步移动，每次移动后比较；如果长度不同，则需要长的那条指针先移动至两条路径长度相同再去比较（如（1））
2. 逆向比较，则最后一个不同的就是最近公共祖先（如（2））当然如果使用递归寻找路径，路径本身就是（2）中的效果，本文采用（2）

代码实现

#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;
}