You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
97 lines
2.2 KiB
97 lines
2.2 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
#pragma region 并查集模板
|
|
int p[101]; //存储元素的父节点
|
|
int Rank[101]; //存储树的高度(秩)
|
|
//建立并查集
|
|
void Build(int n) {
|
|
for (int i = 1; i <= n; ++i) {
|
|
p[i] = i; //父结点是元素自身
|
|
}
|
|
}
|
|
|
|
//查找根结点//路径压缩
|
|
int Find(int x) {
|
|
if (p[x] != x)
|
|
p[x] = Find(p[x]);
|
|
return p[x];
|
|
}
|
|
|
|
//按秩合并集合
|
|
void Union(int x, int y) {
|
|
x = Find(x);
|
|
y = Find(y);
|
|
if (Rank[x] < Rank[y]) p[x] = y;
|
|
else {
|
|
p[y] = x;
|
|
if (Rank[y] == Rank[x]) Rank[x]++;
|
|
}
|
|
}
|
|
|
|
#pragma endregion 并查集模板
|
|
|
|
int main() {
|
|
//输入+输出重定向
|
|
freopen("../1415.txt", "r", stdin);
|
|
|
|
//姓名与编号的映射关系
|
|
unordered_map<string, int> _map;
|
|
unordered_map<int, string> _fanMap;
|
|
|
|
//二维数组,记录父子关系
|
|
vector<vector<int>> v1;
|
|
|
|
int n = 0, k = 0;
|
|
int curParent, curChild;
|
|
string input;
|
|
|
|
vector<string> family;
|
|
vector<string> ask;
|
|
|
|
while (cin >> input) {
|
|
string firstChar = input.substr(0, 1);
|
|
if (firstChar == "$")break;
|
|
//给人名编号
|
|
string name = input.substr(1);
|
|
if (_map.count(name) == 0) {
|
|
n++;
|
|
_map[name] = n;
|
|
_fanMap[n] = name;
|
|
}
|
|
//父亲
|
|
if (firstChar == "#") {
|
|
curParent = _map[name];
|
|
continue;
|
|
}
|
|
//儿子
|
|
if (firstChar == "+") {
|
|
curChild = _map[name];
|
|
k++; //记录关系数量
|
|
//记录关系
|
|
v1.push_back({curParent, curChild});
|
|
}
|
|
//问题
|
|
if (firstChar == "?") {
|
|
ask.push_back(name);
|
|
}
|
|
}
|
|
|
|
//建立并查集
|
|
Build(n);
|
|
//合并集合
|
|
for (int i = 0; i < v1.size(); ++i) {
|
|
curParent = v1[i][0];
|
|
curChild = v1[i][1];
|
|
Union(curParent, curChild);
|
|
}
|
|
//回答问题
|
|
for (int i = 0; i < ask.size(); ++i) {
|
|
cout << ask[i] << " " << _fanMap[Find(_map[ask[i]])] << endl;
|
|
}
|
|
//关闭文件
|
|
fclose(stdin);
|
|
return 0;
|
|
}
|