SSOJ2447家谱
3370+
作者：crxis 发布：2017-09-16 分类：并查集
题目大意：现代的人对于家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
输入
由多行组成：
首先是一些列有关父子关系的描述，其中每一组父子关系由两行组成，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用？name的形式表示要求该人的最早的祖先；
最后用单独的一个$表示输入结束。
规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中记载不超过30代（不止吧？）。
输出
按照输入顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。
样例输入
#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$
样例输出
Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur
解题思路
n个人名，分别保存到s数组中，这n个人的父亲，分别保存到f数组中。遇到“$”符号程序结束；遇到“#”号，记录父亲编号；遇到“+”号，更新儿子的父亲。关键是如何将人名转成编号？这n个人名如何不重复地保存到s数组？可以这样做：每进来一个名字，查找之前所有的n个名字，如果出现一样的，那么名字的编号就是i，否则，找不到的话，在最后面即n+1的位置记录该姓名，名字的编号是n+1，姓名个数也加1。
这样做，速度会比较慢，因为查找的姓名，可能有很多个，n个姓名查找的时间复杂度就是O(n*n)。如何提高速度呢？可以使用哈希表，每次查找只需要O(1)。如果顺序查找的速度是800，那么map的速度就是100，哈希的速度就是10。
另外，题目说不超过30代？这样不压缩路径也是可以的。程序中在查找到后直接输出，你也可以查找归查找，找到祖先后再输出。
程序实现
顺序查找去重：
使用STL中的map：
自己写一个哈希函数：
压缩路径，速度差不多：
