HiHo一下 Week13 最近公共祖先一

HiHo

描述

小Ho最近发现了一个神奇的网站！虽然还不够像58同城那样神奇，但这个网站仍然让小Ho乐在其中，但这是为什么呢？

“为什么呢？”小Hi如是问道，在他的观察中小Ho已经沉迷这个网站一周之久了，甚至连他心爱的树玩具都弃置一边。

“嘿嘿，小Hi，你快过来看！”小Ho招呼道。

“你看，在这个对话框里输入我的名字，在另一个对话框里，输入你的名字，再点这个查询按钮，就可以查出来……什么！我们居然有同一个祖祖祖祖祖爷爷？”

“诶，真是诶……这个网站有点厉害啊。”小Hi不由感叹道。

“是啊，这是什么算法啊，这么厉害！”小Ho也附和道。

“别2，我说的是他能弄到这些数据很厉害，而人类的繁殖树这种层数比较浅的树对这类算法的要求可是简单的不得了，你都能写出来呢！”小Hi道。

“啊？我也能写出来？可是……该从哪开始呢？”小Ho困惑了。

小Ho要面临的问题是这样的，假设现在他知道了N个人的信息——他们的父亲是谁，他需要对于小Hi的每一次提问——两个人的名字，告诉小Hi这两个人的是否存在同一个祖先，如果存在，那么他们的所有共同祖先中辈分最低的一个是谁？

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第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^2，M<=10^2, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人）。

输出

对于每组测试数据，对于每个小Hi的询问，输出一行，表示查询的结果：如果根据已知信息，可以判定询问中的两个人存在共同的祖先，则输出他们的所有共同祖先中辈分最低的一个人的名字，否则输出-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

思路

这道题解法很多，这里数据较小可以用朴素思想，根据条件构建树，每次查询(a,b)的最近公共祖先。把树上所有a的祖先标记，在往上找b的祖先时，输出最早找到的已被标记的那个，若找完b的祖先都没有被标记，那么输出-1。
注意：这里数组要开到200左右，否则会导致越界产生Runtime Error。因为给出的是N个人的父亲，但是这N个人不一定都有联系，所以最多可能有2N个也就是200个人名而不是N+1个。我一开始都没注意到这点，真是大意(´-ι_-｀)

代码

#include<iostream>
#include<string>
#include<bits/stdc++.h>
using namespace std;
string name[202];
int peopleCount=1;
int fa[202]; //Store the father info
bool flag[202]={0}; // Store the labeled ancestors.
//Return ID based on input name
int seekName(string sb){
    for(int i=1;i<peopleCount;i++){
        if (!name[i].compare(sb)) return i;
    }
    name[peopleCount]= string(sb);
    return peopleCount++;
}
//Add father-son relation
void insertRelation(string fat,string son){
    int father = seekName(fat);
    int mySon = seekName(son);
    fa[mySon] = father;
}
//Seek 
void seekPublicAncestor(string jia,string yi){
    int jiaN=seekName(jia);
    int yiN=seekName(yi);
    int i=jiaN;
    while(i!=0){
        flag[i]=1;
        i=fa[i];
    }
    i = yiN;
    while(i!=0){
        if(flag[i]) 
        {
            cout<<name[i]<<endl;
            memset(flag,0,sizeof(flag));
            return;
        }
        i = fa[i];
    }
    cout <<"-1"<<endl;
    //Reset label array
    memset(flag,0,sizeof(flag));
    return ;
}
int main(){
    memset(fa,0,sizeof(fa));
    memset(flag,0,sizeof(flag));
    int n,m;
    string a ,b ;
    cin >>n;    
    for(int i=0;i<n;i++){
        cin >> a;
        cin >> b;
        insertRelation(a,b);
    }
    cin >>m;
    for(int i=0;i<m;i++){
        cin >> a;
        cin >> b;
        seekPublicAncestor(a,b);
    }
    return 0;
}