不会并查集的话请将此文与我以前写的并查集一同食用。
原题来自洛谷
原题
文字稿在此：
题目背景
现代的人对于本家族血统越来越感兴趣。
题目描述
给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
输入输出格式
输入格式：
输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。
输出格式：
按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。
输入输出样例
输入样例#1：
#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$
输出样例#1：
Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur
说明
规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。
map
map是STL中的一种数据结构，你可以理解为它是一个下表不一定 为整形的数组（也就是说，下表可以为字符、字符串。。。）
map类型的声明
大体模式式是
map<下标类型，数组每一个元素的类型> 数组名;
比如说我要一个下表是字符串，每一个元素的类型也是字符串，名字叫a的数组，我可以这样写
map<string,string> a;
回到题目
会了map，相信你应该也有点思路了吧？这是 建立在并查集基础上的，不会并查集的话，可以看看我以前写的并查集。
有了map我们就可以使用 真正意义上的字符串数组来编程了！！！
函数
这里面的getfather函数 变异了，他成了这样
string getfather(string x)//找x的根结点
{//这其实是一个递归函数
if(father[x]!=x)
{
return getfather(father[x]);//它会一级一级找上去（先找到它爸爸，在找到它爸爸的爸爸，再找到它爸爸的爸爸的爸爸。。。。。）
}
else
{
return father[x];//边界条件，如果x的根结点就是x（也就是说它没有更上边的祖宗了）
}
}
相较以前的getfather，首先函数的类型成了string，而且x的类型也是string。但是作用和以前是一样的。
读入
这题的读入很特殊，因为这道题要边读入边处理边输出
char c;//就是名字 前面那个字符
string s,fat;//s是名字，fat是是用来暂存先提及的父亲的名字的
这题我用了这几个变量。
核心代码如下
map<string,string> father;//用来存储某一点的根结点
cin>>c;//读入c
while(c!='$')//只要c不是$就会执行
{
cin>>s;//读入名字
if(c=='#')//假如读到了父亲 的名字
{
fat=s;//fat暂存父亲的名字，因为过一会儿s的值会变
if(father[s]=="") father[s]=s;//如果father[s]的值为空，也就是说s就是自己的根结点（找到底了）
}
if(c=='+')//如果s是表示儿子
{
father[s]=fat;//s的根结点就成了fat（上面说的fat这是就派上了用场）
}
if(c=='?')//查集
{
cout<<s<<' '<<getfather(father[s])/*输出father[s]的根结点*/<<endl;
}
cin>>c;//读入c，开始新一轮的循环
}
完整程序如下
#include<map>
#include<iostream>
using namespace std;
map<string,string> father;
string getfather(string x)
{
if(father[x]!=x)
{
return getfather(father[x]);
}
else
{
return father[x];
}
}
int main()
{
char c;
string s,fat;
cin>>c;
while(c!='$')
{
cin>>s;
if(c=='#')
{
fat=s;
if(father[s]=="") father[s]=s;
}
if(c=='+')
{
father[s]=fat;
}
if(c=='?')
{
cout<<s<<' '<<getfather(father[s])<<endl;
}
cin>>c;
}
return 0;
}
总结
这题其实和并查集的模版的差异并不大，只是涉及到STL中的数据结构map的使用。所以对于提高+的评价感觉是过了点，但要是不会map的话可能真的是这个难度了。
如果字符串功底够好，也可以 考虑用字符串/字符 数组来实现（我字符串功底不好。。）
tks。
