hihoCoder 1062-最近公共祖先·一

hihoCoder 1062-最近公共祖先·一

#1062 : 最近公共祖先·一
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述
小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


最近公共祖先问题:给定一个家谱图,问某两个人的最近的公共祖先是谁,如果没有公共祖先,输出-1。最简单的方法题目提示得很清楚了:

当然你也先将一个人的祖先全都标记出来,然后顺着另一个的父亲一直向上找,直到找到第一个被标记过的结点,便是它们的最近公共祖先结点了。

所以我就简单粗暴的使用STL的MAP和SET来解决问题了。假设需要判断的两个人名分别为son1和son2,那么①首先把*son1*及其所有祖先都找到并加入到一个set中,然后②首先判断son2在不在前面的set中,③如果不在,再依次判断son2的祖先在不在set中。

这里需要注意几点:
1. son1的祖先包括son1本身,比如第二个样例中的JiaBaoyu和JiaZheng,JiaZheng的祖先就包括JiaZheng自己,所以需要上面的第①和②步。
2. 为什么使用set而不是vector呢?因为②③步需要在son1的祖先中搜索,set内部用红黑树实现,搜索的效率高于vector。

知道了以上几点,就可以很快的写出代码了,完整代码如下:

#include<iostream>
#include<map>
#include<string>
#include <set>
using namespace std;
int main()
{
     //freopen("input.txt","r",stdin);

     int n,t;
     cin>>n;
     string son,father;
     map<string,string> son_father;//map[son]=father
     for(int i=0;i<n;i++)
     {
          cin>>father>>son;
          son_father.insert(make_pair(son,father));
     }
     cin>>t;
     string son1,son2,comm_father;
     while(t--)
     {
          comm_father="";
          cin>>son1>>son2;
          //vector<string> grand_fathers;
          set<string> grand_fathers;//使用set的查找效率高于vector
          grand_fathers.insert(son1);//注意,son1,son2本身也是一个祖先,一定要加进去,否则错!
          while(son_father.find(son1)!=son_father.end())
          {
               grand_fathers.insert(son_father[son1]);
               son1=son_father[son1];
          }
          if(grand_fathers.find(son2)!=grand_fathers.end())//首先son2本身也是一个祖先,所以先判断一下//使用set的查找效率高于vector
          {
               if(t!=0)
                    cout<<son2<<endl;
               else
                    cout<<son2;
               continue;
          }
          while(son_father.find(son2)!=son_father.end())
          {
               if(grand_fathers.find(son_father[son2])!=grand_fathers.end())
               {
                    comm_father=son_father[son2];//因为是son2从下往上找,所以第一个出下的肯定是最近的公共祖先
                    break;
               }
               else
                    son2=son_father[son2];
          }
          if(t!=0)
          {
               if(comm_father=="")
                    cout<<"-1"<<endl;
               else
                    cout<<comm_father<<endl;
          }
          else
          {
               if(comm_father=="")
                    cout<<"-1";
               else
                    cout<<comm_father;
          }
         
     }
     return 0;
}

本代码提交AC,用时4MS,内存0MB。

之前说了,我这种解法是非常简单粗暴的,事实上最近公共祖先问题是一个经典问题,有很多经典算法可以解决,我后面会进一步研究。

One thought on “hihoCoder 1062-最近公共祖先·一

  1. Pingback: hihoCoder 1067-最近公共祖先·二 | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *