hihoCoder 1067-最近公共祖先·二

hihoCoder 1067-最近公共祖先·二

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

描述
上上回说到,小Hi和小Ho用非常拙劣——或者说粗糙的手段山寨出了一个神奇的网站,这个网站可以计算出某两个人的所有共同祖先中辈分最低的一个是谁。远在美国的他们利用了一些奇妙的技术获得了国内许多人的相关信息,并且搭建了一个小小的网站来应付来自四面八方的请求。

但正如我们所能想象到的……这样一个简单的算法并不能支撑住非常大的访问量,所以摆在小Hi和小Ho面前的无非两种选择:

其一是购买更为昂贵的服务器,通过提高计算机性能的方式来满足需求——但小Hi和小Ho并没有那么多的钱;其二则是改进他们的算法,通过提高计算机性能的利用率来满足需求——这个主意似乎听起来更加靠谱。

于是为了他们第一个在线产品的顺利运作,小Hi决定对小Ho进行紧急训练——好好的修改一番他们的算法。

而为了更好的向小Ho讲述这个问题,小Hi将这个问题抽象成了这个样子:假设现小Ho现在知道了N对父子关系——父亲和儿子的名字,并且这N对父子关系中涉及的所有人都拥有一个共同的祖先(这个祖先出现在这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^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


hihoCoder确实是个练习算法的好网站,之前我们写过朴素的最近公共祖先问题:hihoCoder Problem 1062: 最近公共祖先·一,但那是一个效率比较低的方法,这一次,hihoCoder详细给我们介绍了最近公共祖先的离线算法,而且讲解非常详细。

网站上的讲解详细,易于理解,我这里简单概括一下。所谓离线算法就是先把询问搜集起来,如果某个询问能先回答,则记录答案,直到把所有询问都解答了;与之相对的是在线算法,也就是每提出一个询问,我都要实时的马上回答。

离线算法综合了DFS和并查集。给定一个族谱(树形结构),我们先把每一个节点染成白色,并且在初始并查集中,每个点都是一个独立的集合,然后从树根开始深度优先遍历,当第一次经过某个节点a的时候,把它由白色改为灰色;如果第二次访问该节点的时候(也就是离开该点的时候),则把它由灰色改为黑色。

当a每次由白变灰之后,查看询问中是否出现过该节点,如果出现了,则查看询问中另一个节点b的颜色,如果b是灰色,则<a,b>的最近公共祖先就是b,因为b是灰色的,所以访问a之前肯定访问了b,所以它们的最近公共祖先是b;如果b是黑色,此时已经离开b了,并不能直接说明a和b的关系,但是<a,b>的最近公共祖先肯定在灰色链上,所以我们只要找出b向上的第一个灰色节点,就是<a,b>的最近公共祖先;如果b是白色,则说明b还没有访问,没有关于b的信息,所以我们暂时不管这个询问,等到访问到b时,a肯定不是白色,这是可以依据前两条规则得出它们的最近公共祖先。

当a每次由灰变黑之后,我们需要在并查集中将a和a的直接父节点合并UNION,因为当a由灰变黑时,a及其子树都访问结束了,但是a的直接父节点还没有访问结束,也就是说a的直接父节点还是灰色的,这样我们就记录了a向上的第一个灰色节点,这为上面的第二种情况判断做准备。

最近公共祖先的离线算法概括起来就是上面的内容,简单易懂也很强大。但是因为算法既包含DFS,又包含并查集,对初学者来说有一定的难度,而且这个题给出的数据是字符串形式的,数据量又很大,有很多细节需要注意。

我先把完整的代码贴出来,然后讲一下主要过程。

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

const int MAX_N=100010;//最大人数

map<string,int> name_index;//名字转换为数字
vector<string> index_name(MAX_N);//数字转换为名字
int color[MAX_N]={0};//0:白;1:灰;2:黑,初始颜色都是白色
int s_f[MAX_N];//son_father。s_f[i]表示第i个儿子的直接父亲
vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子
vector<vector<int> > show_at(MAX_N);//show_at[i]表示第i个人在哪些询问里出现过
int q_l[MAX_N];//第i个询问的左边
int q_r[MAX_N];//第i个询问的右边
int father[MAX_N];//用于并查集,和s_f不一样
vector<string> ans;//最终结果

//保存某个人的信息,并返回其下标
int store_name(string name)
{
     map<string,int>::iterator it=name_index.find(name);
     if(it==name_index.end())//还不存在
     {
          int curr_index=name_index.size();//用当前已有人数作为其下标,正好是递增的。
          name_index.insert(make_pair(name,curr_index));
          index_name[curr_index]=name;//记录
          father[curr_index]=curr_index;//初始的时候,并查集中每个元素都是一个独立的集合
          return curr_index;//返回下标
     }
     else
          return it->second;//已经存在,直接返回
}

//并查集FIND操作
int find_father(int name)
{
     return name==father[name]?name:(father[name]=find_father(father[name]));
}

//并查集UNION操作
void union_father(int name1,int name2)
{
     father[find_father(name1)]=find_father(name2);
}

//深度遍历族谱树
void DFS(int root)
{
     color[root]=1;//首先修改颜色为灰色
     int show_time=show_at[root].size();//查看该元素是否在询问里出现
     if(show_time!=0)
     {
          for(int i=0;i<show_time;i++)//判断所有询问
          {
               int column=show_at[root][i];
               int left=q_l[column];//找到该询问的左右元素
               int right=q_r[column];
               if(left==right)//如果是左右相同,则该自身即是其最近公共祖先
                    ans[column]=index_name[left];
               else
               {
                    if(left==root)//判断当前访问的是左边的还是右边的
                    {
                         if(color[right]==1)//另一个点为灰色
                              ans[column]=index_name[right];//结果即为该灰色点
                         else if(color[right]=2)//另一个点为黑色
                              ans[column]=index_name[find_father(right)];//找其向上最近的灰色节点
                    }
                    else
                    {
                         if(color[left]==1)//另一个点为灰色
                              ans[column]=index_name[left];
                         else if(color[left]=2)//另一个点为黑色
                              ans[column]=index_name[find_father(left)];
                    }
               }
          }
     }

     int sons=f_s[root].size();//查看是否有孩子节点
     if(sons!=0)
     {
          for(int i=0;i<sons;i++)
               DFS(f_s[root][i]);//深度遍历其所有孩子
     }
     color[root]=2;//改颜色为黑色
     union_father(root,s_f[root]);//和直接父节点UNION
}
int main()
{
     ios_base::sync_with_stdio(false);//取消同步,加速
     cin.tie(0);

     //freopen("input.txt","r",stdin);

     int n,m;
     string name1,name2;
     int index1,index2;
     cin>>n;
     while(n--)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          f_s[index1].push_back(index2);
          s_f[index2]=index1;
     }

     cin>>m;
     ans.resize(m);
     for(int i=0;i<m;i++)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          q_l[i]=index1;
          q_r[i]=index2;
          show_at[index1].push_back(i);
          show_at[index2].push_back(i);
     }
     DFS(0);
     for(int i=0;i<m;i++)
          cout<<ans[i]<<endl;
     return 0;
}

摆在我们面前的第一个问题就是数据的输入问题,题目给的每个人名都是字符串,当然我们可以直接用字符串构建一个树结构,然后进行查找、比较、赋值等操作,但是这样的时空效率都比较低,所以我们可以先用map<string,int> name_index和vector<string> index_name来记录人名字符串和人名数字下标,这样我们在DFS+并查集的时候可以只使用数字下标,到最后输出的时候再转换为字符串,提高效率。记录并返回人名数字下标的操作在函数int store_name(string name);中。

我们还需要记录父子关系,因为一个父亲可以有多个孩子,所以父亲-孩子关系需要用二维数组vector<vector<int> > f_s(MAX_N);来表示;而一个孩子只可能有一个父亲,所以孩子-父亲关系可以用一维数组int s_f[MAX_N];来表示。

还有两个数组需要初始化,每个节点的颜色初始化为白色,在并查集中每个节点单独为一个集合。

然后就是存储询问了。正如前面对LCA离线算法的描述,每当一个节点从白色变为灰色时,我们都要查看询问中是否出现过该节点。输入的询问中有很多节点,怎样来快速判断所有询问中是否有某个节点以及该询问中的另一个节点呢?如果这个问题处理不好,很可能就是TLE,反正我前两个版本都是因为这个原因TLE的。

这个问题可以通过两个步骤来解决,都是用空间来换时间。因为每一个询问都是由左右两个人名组成的,那么我们先把每次询问的左右两个人名记录在int q_l[MAX_N];和int q_r[MAX_N];中。然后还用一个二维数组vector<vector<int> > show_at(MAX_N);来记录某一个节点在哪些询问里出现过。这样当我们DFS到某个节点a时,首先查看show_at[a]这个数组是否为空,如果为空,说明a没有出现在任何一次询问中;如果不为空,则show_at[a]记录了a出现的所有询问的序号,根据这个序号,我们再去查q_l和q_r,这样就可以取出a出现时的那个询问的左右两个人名是什么了。所以整个过程只需要O(1)的时间,大大提高了时间效率。

因为题目中说明了

第一个出现的名字所确定的人是其他所有人的公共祖先。

所以我们以第一个人名下标0来DFS树结构。DFS的过程和上面的算法描述一致,我这里就不多说了,代码中都有详细的注释。

还有一个小问题需要注意,因为编译器不一样,在用vector声明二维数组的时候,我在VS2010下可以这样:

vector<vector<int>> a; //sth

但是提交之后会报Compile Error的错误:error: ‘>>’ should be ‘> >’ within a nested template argument list,也就是说这个编译器把>>看成了移位操作符,所以我们在两个箭头之间加一个空格> >这样就没问题了。

我上面的代码版本提交后AC,用时711MS,内存30MB。这是我迄今为止内存消耗最大的一次AC。

总的来说,这个题是好题,很考验选手的综合能力,特别是本题用到的各种数据结构较多,需要全盘考虑,不断优化。

One thought on “hihoCoder 1067-最近公共祖先·二

  1. Pingback: POJ 1330-Nearest Common Ancestors | bitJoy > code

Leave a Reply

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