使用RMQ-ST算法解决最近公共祖先问题

发表于 | 分类于 | | 阅读次数:

之前我们曾介绍了两种求解最近公共祖先的方法【链接】，分别使用了并查集方法和DFS深度优先遍历的方法，其中并查集方法虽然思路简单，但是时间效率并不高，只适用于样本值较少的情况下，而对于深度优先遍历DFS这种离线算法我们很难决定是当有询问发生的时候旧进行遍历求解还是等待一定数量的请求之后再进行遍历求解，毕竟无论多次请求还是一次请求，我们的求解过程都是进行一趟遍历。
所以我们希望只针对一个询问就可以开展计算，同时还要有着较高的时间效率，所以本文将介绍一种使用RMQ-ST算法的在线求解算法，关于RMQ-ST算法可以参考上篇博文【链接】。

题目描述

【输入】
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为一个整数N，意义如前文所述。
每组测试数据的第2~N+1行，每行分别描述一对父子关系，其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i，分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M，表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行，每行分别描述一个询问，其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i，分别表示小Hi询问中的两个名字。
对于100%的数据，满足N<=10^5，M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人），所有询问中出现过的名字均在之前所描述的N对父子关系中出现过，且每个输入文件中第一个出现的名字所确定的人是其他所有人的公共祖先。
【输出】
对于每组测试数据，对于每个询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：他们的所有共同祖先中辈分最低的一个人的名字。
【样例输入】

4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin

【样例输出】

Sam
Adam
Adam

解题思路

  • 最近公共祖先其实就是树结构中两点连线的折点；
  • 也就是说是两点路径中深度最小的那个点；
  • 通过使用深度优先遍历，遍历整棵树，每当进入一个结点就将其记录下来，离开的时候即他所在的分支已遍历完成，则将其父亲结点记录下来，从而完成从树结构到数组的转换；
  • 使用RMQ-ST算法对此数组进行求解，求出状态方程；
  • 对于给定的询问，只需要计算其遍历区间，然后使用RMQ-ST算法取其中的深度最小值，最后将对应结点字符串打印出来即可。

最终代码

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <algorithm>
#include <map>
#define N 100010
using namespace std;

typedef struct node
{
    string name;
    int depth;
    int id;
    node* father;
    vector<node*> child;
    node(string name_) : name(name_)
    {
        depth = 0;
        id = 0;
        father = NULL;
    }
}*Node;

int n, m;
int cnt = 0;
int num = 0;
Node root = NULL;
map<string, Node> tree;//储存树结构
map<string, int> seq;//储存询问字符串与序号的映射
map<int, string> seq2;//与seq相反的映射
vector<pair<int, int>> dp[19];//储存RMQ-ST的状态信息

void dfs(Node p, int d)
{
    p->depth = d;
    p->id = num++;

    seq[p->name] = cnt;
    seq2[cnt] = p->name;
    dp[0].push_back(make_pair(p->depth, cnt++));

    for(int i = 0; i < p->child.size(); ++i)
    {
        dfs(p->child[i], d+1);
    }

    if(p->father)
    {
        seq[p->father->name] = cnt;
        seq2[cnt] = p->father->name;
        dp[0].push_back(make_pair(p->father->depth, cnt++));
    }
}

void st()
{
    //因为是n行，对应n+1个结点，所以是2 × n + 1
    int k = log2(2 * n + 1);
    for(int i = 1; i <= k; ++i)
    {
        for(int j = 0; j + (1<<i) - 1 < 2 * n + 1; ++j)
        {
            int next = j + (1<<(i-1));
            if(dp[i-1][j].first < dp[i-1][next].first)
                dp[i].push_back(dp[i-1][j]);
            else
                dp[i].push_back(dp[i-1][next]);
        }
    }
}

int main()
{
    string s1, s2;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> s1 >> s2;
        if(tree.find(s1) == tree.end())
            tree[s1] = new node(s1);
        if(tree.find(s2) == tree.end())
            tree[s2] = new node(s2);
        tree[s1]->child.push_back(tree[s2]);
        tree[s2]->father = tree[s1];
        if(i == 0)
            root = tree[s1];
    }

    dfs(root, 0);
    st();

    cin >> m;
    while(m--)
    {
        cin >> s1 >> s2;
        int l, r, res, temp;
        l = seq[s1];
        r = seq[s2];
        if(l > r)  //这里需要判断输入的字符串的顺序
            swap(l, r);
        int k = log2(r - l + 1);
        if(dp[k][l].first < dp[k][r - (1<<k) + 1].first)
            res = dp[k][l].second;
        else
            res = dp[k][r - (1<<k) + 1].second;
        cout << seq2[res] << endl;
    }
    return 0;
}

总结

  • 这道题目完全按照自己的思路一直写下去，写了一天，最后终于AC的时候激动的都要拍桌子了，太有成就感了！
  • 所有的问题只要肯下功夫，一点一点理清思路，都是可以做出来的，后面优化可以参考别人的代码。所以写代码一定要耐心，细心，按照思路一点一点抽丝剥茧。
  • 写代码的时间不一定要很长，思考才是最重要的，思路清晰才是我们解决问题的根本！
  • 解决bug的时候一定要耐心，多顺几遍思路，不会GDB就多用打印cout，一点点排查错误。不能AC就一定有问题，有问题就一定有解决办法！
  • 写代码需要多写多练多读，需要的是时间的积累和经验的总结，所以要坚持、多写、多多总结！
-------------本文结束感谢您的阅读-------------
0%