Hihocoder 1062 最近公共祖先1

题意：给出N条父子关系，询问M条两人最近公共祖先，没有就输出-1.
分析：
用map 每个儿子映射父亲，
开始找最近的公共祖先，先找第一个人的祖先，所有祖先都标记；
然后从第二个人开始找，如果找到被标记的，就是他们最近的公共祖先，输出，
如果第二个人的祖先找完也没有找到，那就没有公共的祖先，输出-1

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
typedef unsigned long long ULL;
using namespace std;

bool Sqrt(LL n) { return (LL)sqrt(n) * sqrt(n) == n; }
const double PI = acos(-1.0), ESP = 1e-10;
const LL INF = 99999999999999;
const int inf = 999999999;
int n, m;
string a, b;
map<string, string> fa;

void Run(string a, string b)
{
    map<string, bool> vis;
    vis[a] = 1;
    while(fa[a].size()) {
        vis[fa[a]] = 1;
        a = fa[a];
    }
    while(b.size()) {
        if(vis[b]) { cout << b << "\n"; return ;}
        b = fa[b];
    }
    puts("-1");
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    while(n--) {
        cin >> a >> b;
        fa[b] = a;
    }
    scanf("%d", &m);
    while(m--) {
        cin >> a >> b;
        Run(a, b);
    }

    return 0;
}
/*
    input:
    output:
    modeling:
    methods:
    complexity:
    summary:
*/

Hihocoder 1062 最近公共祖先1

原文：https://www.cnblogs.com/000what/p/11666714.html