最近公共祖先问题

最近公共祖先问题，即LCA（Lowest Common Ancestors）问题，是一个基于并查集和深度优先搜索的算法问题。题目假设我们已经知道了N个人的信息——他们的父亲是谁，然后对任意输入的两个人名，给出这两个人公共祖先中辈分最低的一个祖先。

并查集方法

题目介绍

输入输出介绍和样例如下，题目出自hihoCoder。（点击查看原题介绍讲述）
【输入】
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第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，分别表示询问中的两个名字。
对于100%的数据，满足N<=10^2，M<=10^2, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人）。
【输出】
对于每组测试数据，输出一行，表示查询的结果：如果根据已知信息，可以判定询问中的两个人存在共同的祖先，则输出他们的所有共同祖先中辈分最低的一个人的名字，否则输出-1。
【样例输入】

11
JiaYan JiaDaihua
JiaDaihua JiaFu
JiaDaihua JiaJing
JiaJing JiaZhen
JiaZhen JiaRong
JiaYuan JiaDaishan
JiaDaishan JiaShe
JiaDaishan JiaZheng
JiaShe JiaLian
JiaZheng JiaZhu
JiaZheng JiaBaoyu
3
JiaBaoyu JiaLian
JiaBaoyu JiaZheng
JiaBaoyu LinDaiyu

【样例输出】

JiaDaishan
JiaZheng
-1

题目分析

使用map<string, string>存储两个名字之间的辈分关系；

使用map<string, int>存储其中一个人名的迭代查找结果，其中int只是为了创建map；

对第二个人名进行迭代查找，若查找结果在map<string, int>中，则直接打印即为最近公共祖先；

最终代码

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    int n, p;
    cin >> n;
    string fa, son, s1, s2;
    map<string, string> m;
    map<string, string>::iterator it;
    map<string, int> vec;
    for(int i = 0; i < n; ++i)
    {
        cin >> fa >> son;
        m.insert(make_pair(son, fa));
    }
    cin >> p;
    while(p--)
    {
        vec.clear();
        cin >> s1 >> s2;
        vec.insert(make_pair(s1, 0));
        it = m.find(s1);
        while(it != m.end())
        {
            vec.insert(make_pair((*it).second, 0));
            it = m.find((*it).second);
        }
        if(vec.find(s2) != vec.end())
        {
            cout << s2 << endl;
            continue;
        }
        it = m.find(s2);
        while(it != m.end())
        {
            if(vec.find((*it).second) != vec.end())
            {
                cout << (*it).second << endl;
                break;
            }
            else
                it = m.find((*it).second);
        }
        if(it == m.end())
            cout << -1 << endl;
    }
    return 0;
}

总结

使用上述方法由于需要对数据进行遍历，所以时间效率很低，在用户样本信息较少的情况下比较适用。

深度优先搜索

由于上述方法只使用与样本数量较少的情况下，所以接下来我们提出一种能够应用于大样本的深度优先搜索的算法。

题目描述

题目描述与上一题目基本一致，同样来源hihoCoder，题目详情请点击查看。
【输入】
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第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对父子关系中出现过，第一个出现的名字所确定的人是其他所有人的公共祖先。
【输出】
对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：他们的所有共同祖先中辈分最低的一个人的名字。
【样例输入】

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

【样例输出】

Sam
Adam
Adam

题目分析

通过对家族树的各个结点进行深度优先遍历，没有遍历到的树的颜色为白色（0），第一次遍历之后为灰色（1），离开时置为黑色（2）；

遍历至一请求结点A，将其置为灰色，若其对应的询问结点B为白色，则未询问到次结点，继续深度遍历；

若对应询问结点B为灰色，则两个询问结点在同一分支上，则深度优先搜索尚未离开分支，取请求结点A的名字即为公共祖先；

若对应询问结点B为黑色，则深度优先搜索已经离开该询问结点B，取该黑色结点B的上一个结点名字即为公共祖先；
建立如下node结点：
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct node
{
    string name;
    node* father;
    int color;
    vector<node*> child;
    node(string name_) : name(name_)
    {
        father = NULL;
        color = 0;
    }
}*Node;

使用map<string, Node>存储名字与结点的映射关系；使用map<string, vector<pair<Node, int>>>存储询问结点姓名与结点、序号的映射关系。

最终代码

#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;
#define N 100010

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

string res[N];
map<string, Node> tree;
map<string, Node>::iterator it;
typedef pair<Node, int> NodeNum;
map<string, vector<NodeNum>> query;

Node findRoot(Node p)
{
    if(p->color == 1)
        return p;
    else
    {
        p->father = findRoot(p->father);
        return p->father;
    }
}

void dfs(Node p)
{
    p->color = 1;
    vector<NodeNum> &pChild = query[p->name];
    for(int i = 0; i < pChild.size(); ++i)
    {
        Node pQuery = pChild[i].first;
        int id = pChild[i].second;
        if(pQuery->color == 0)
            continue;
        res[id] = findRoot(pQuery)->name;
    }

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

int main()
{
    Node root = NULL;
    string s1, s2;
    int n, m;
    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];
    }

    cin >> m;
    for(int i = 0; i < m; ++i)
    {
        cin >> s1 >> s2;
        if(query.find(s1) == query.end())
            query[s1] = vector<NodeNum>();
        if(query.find(s2) == query.end())
            query[s2] = vector<NodeNum>();
        Node p1 = tree[s1];
        Node p2 = tree[s2];
        query[s1].push_back(make_pair(p2, i));
        if(s1 != s2)
            query[s2].push_back(make_pair(p1, i));
    }

    dfs(root);

    for(int i = 0; i < m; ++i)
        cout << res[i] << endl;
    return 0;
}

总结

使用这种深度优先搜索的方法，同时兼顾使用了并查集的思想维护遍历过程中的辈分关系，能够高效地处理较大数据量的公共祖先问题；

map实在是太好用了，可以建立各种类型之间的映射关系，使用map[key]还可以直接取出<key, value>中的value，即map[key] = value，大大方便了信息的存储与管理；

首次遍历到结点，将其置为灰色（1），离开该结点时将其置为黑色（2），这种分析问题的方法非常值得借鉴使用。