博客

【题目链接】

ybt 1388：家谱(gen)
洛谷 P2814 家谱

【题目考点】

1. STL map

2. 并查集

【解题思路】

解法1：把名字转为整数

设置将名字与整数互相转换的映射。name2Num保存的键值对为(名字，编号)。可以将名字转为编号。
num2Name保存的键值对为(编号，名字)，可以将编号转为名字。
每输入一个名字，都先检查一下name2Num中是否有以该名字为键的键值对（即该名字是否出现过），如果之前没出现过，则为该名字分配一个新的编号。而后该名字对应的编号为name2Num[名字]

每个人都是用一个整数来表示的，那么就可以用树的双勤表示法（也就是并查集中的fa数组）来表示所有人之间的关系。
fa[x]为编号为x的人的父亲的编号。

• 如果输入的是父亲，用fatherNum记录父亲编号，在后面输入儿子时会用到。
• 如果输入的是儿子，那么把儿子编号x的父亲设为fatherNum，即fa[x] = fatherNum
• 如果查询某人多祖先，写出并查集中的查询函数find，find(x)的返回值即为x的祖先。

解法2：直接使用字符串

设map<string, string> fa，fa[x]表示名字为x的人的父亲的名字。
模仿并查集中的查询操作，写出find函数，求x的祖先。

• 如果输入的名字是父亲，且第一次出现。将该名字保存在father变量中，那么类似并查集中的做法，把father的父亲设为自己，即fa[father] = father。
• 如果输入的名字是儿子，保存在child变量中。父亲名字已经保存在father变量，那么设父子关系fa[child] = father。
• 如果要查询一个人的祖先，调用find函数。

【题解代码】

解法1：把名字转为整数

#include <bits/stdc++.h>
using namespace std;
#define N 50005
map<string, int> name2Num;//name2Num[名字]：编号 
map<int, string> num2Name;//num2Name[编号]：名字 
int fa[N];
void init(int n)
{
	for(int i = 1; i <= n; ++i)
		fa[i] = i;
}
int find(int x)
{
	if(x == fa[x])
		return x;
	else
		return fa[x] = find(fa[x]);
}
int n;
int main()
{
	int fatherNum;
	char c;
	string s;
	init(50000);
	while(cin >> c >> s && s != "$")
	{
		if(c == '#')
		{
			if(name2Num.count(s) == 0)//如果不存在键s，添加键值对(s, n+1)，否则不插入新的键值对。 
			{ 
				name2Num[s] = ++n;
				num2Name[n] = s;
			}
			fatherNum = name2Num[s];
		}
		else if(c == '+')
		{
			if(name2Num.count(s) == 0)
			{
				name2Num[s] = ++n;
				num2Name[n] = s;
			}
			fa[name2Num[s]] = fatherNum;//设置父子关系 
		}
		else//c == '?' 认给定的名字都是已经存在的 
			cout << s << ' ' << num2Name[find(name2Num[s])] << endl;
	}
	return 0;
}

解法2：直接使用字符串

#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;
}