A28815. 家谱(gen)
填空题
困难
知识点
题目描述
家谱(gen)
题目描述
现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
输入
由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#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参考答案
#include <bits/stdc++.h>
using namespace std;
#define N 50005
map<string, string> fa;//fa[儿子]：父亲
string find(string x)
{
if(fa[x] == x)
return x;
else
return fa[x] = find(fa[x]);
}
int main()
{
char c;
string father, child;
while(cin >> c && c != '$')
{
if(c == '#')
{
cin >> father;
if(fa.count(father) == 0)
fa[father] = father;
}
else if(c == '+')
{
cin >> child;
fa[child] = father;
}
else if(c == '?')
{
cin >> child;
cout << child << ' ' << find(child) << endl;
}
}
return 0;
}答案解析
设map<string, string> fa，fa[x]表示名字为x的人的父亲的名字。
模仿并查集中的查询操作，写出find函数，求x的祖先。
如果输入的名字是父亲，且第一次出现。将该名字保存在father变量中，那么类似并查集中的做法，把father的父亲设为自己，即fa[father] = father。
如果输入的名字是儿子，保存在child变量中。父亲名字已经保存在father变量，那么设父子关系fa[child] = father。
如果要查询一个人的祖先，调用find函数。
上一题
下一题