思路

一眼模拟题，照做就行

用到的知识：路径压缩

路径压缩：每次找祖先时把爸爸改成祖先，这样多次查询就不用再跑一遍了

代码

#include <bits/stdc++.h>
using namespace std;
map<string,string> fa;
string find(string x){
	if (x == fa[x])	return x;
	return fa[x] = find(fa[x]);
}
int main(int argc, char **argv){
	char op;string f;
	cin >> op;
	do{
		string s;
		cin >> s;
		if (op == '#'){
			f = s;
			if (fa[f] == "")	fa[f] = f;
		}
		else if (op == '+')	fa[s] = f;
		else if (op == '?')	cout << s << ' ' << find(s) << '\n';
		cin >> op;
	}while (op != '$');
	return 0;
}

A1388 家谱（gen）

洛谷编号：P2814

题干

要求并查集求根节点

难度

本题的输入都是string，所以用数组的方法就fail掉了（数组编号不能是string），我们需要新的方法处理数据

思路

除了数组以外，还有什么stl数据结构能建立两者之间的有效关系呢？

我们自然而然的想到了map（类似python的dictionary（字典））

这里给不知道什么是map的同学们普及一下该数据结构：

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。

具体百科地址：点我

知道了map的特性和用法后，我们就可以写出并查集中的求根函数：（p是一个map）

string Get(string x){return p[x]==x?x:p[x]=Get(p[x]);}

并集的话，只需要改变名字前的key（即父亲）即可。

代码+解析

#include<bits/stdc++.h>
using namespace std;
map<string,string>p;//由map建立父子关系链
string Get(string x){return p[x]==x?x:p[x]=Get(p[x]);}//求根函数，与int形式的get差不多
int main(){
	char start;string name,name2;//需要的变量
	cin>>start;//这里用的是cin，因为使用scanf的时候出现了一些bug，printf/cout亦然（不知道为什么，有没有大佬可以在评论区解答）
	while(start!='$'){//while循环（条件，start（即首字符）不为$）
		cin>>name;//名字
		if(start=='#'){if(p[name]=="")p[name]=name;name2=name;}//当一个人是父亲的时候，如果他没有父亲，他就是他们家族的祖先，name2交给后面的儿子用
		else if(start=='+')
			p[name]=name2;//如果是儿子，那么key就是父亲（name2存储父名）
		else
			cout<<name<<' '<<Get(name)<<endl;//如果输入？，那么直接按格式输出
		cin>>start;//别忘了重启下一轮循环！
	}
	return 0;//自信递交！
}

另附洛谷题解地址（参考过）：点我

求点赞

如果有大佬有更好的方法，本人必定点赞+orz