题解：洛谷 P2814 家谱

【题目来源】

洛谷：P2814 家谱 - 洛谷

【题目描述】

给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

【输入】

输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用 #name 的形式描写一组父子关系中的父亲的名字，用 +name 的形式描写一组父子关系中的儿子的名字；接下来用 ?name 的形式表示要求该人的最早的祖先；最后用单独的一个 $ 表示文件结束。

【输出】

按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式为：本人的名字 + 一个空格 + 祖先的名字 + 回车。

【输入样例】

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

【输出样例】

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

【解题思路】

【算法标签】

《洛谷 P2814 家谱》 #字符串# #搜索# #图论# #线性数据结构# #并查集#

【代码详解】

#include <bits/stdc++.h>
using namespace std;const int N = 50005;  // 定义最大人数int p[N];             // 并查集父节点数组
string name[N];       // 存储人名
string s;             // 临时输入字符串
map<string, int> mp;  // 人名到ID的映射
int id = 1, fa;       // id: 当前可用ID, fa: 当前父亲节点ID/*** 查找根节点（带路径压缩）* @param x 当前节点* @return 根节点*/
int find(int x)
{return p[x] == x ? x : p[x] = find(p[x]);
}int main()
{// 初始化并查集for (int i = 1; i <= 49999; i++) {p[i] = i;}// 处理输入直到遇到'$'while (1) {cin >> s;if (s[0] == '$') break;  // 结束标志string tmp = s.substr(1);  // 提取人名部分if (s[0] == '#') {// 处理父亲节点if (mp.count(tmp) == 0) {// 新人名，分配IDmp[tmp] = id;name[id] = tmp;fa = id;id++;} else {// 已存在的人名，查找其根节点fa = find(mp[tmp]);}} else if (s[0] == '+') {// 处理孩子节点if (mp.count(tmp) == 0) {// 新人名，分配ID并设置父亲mp[tmp] = id;name[id] = s;p[id] = fa;id++;} else {// 已存在的人名，设置其父亲p[mp[tmp]] = fa;}} else if (s[0] == '?') {// 查询祖先cout << tmp << " " << name[find(mp[tmp])] << endl;}}return 0;
}

【运行结果】

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
Edward Arthur
?Walter
Walter Arthur
?Rodney
Rodney George
?Arthur
Arthur Arthur
$