这个题不难，但是有点小小坑。
首先并查集肯定能看出来。
然后字符串的话，一开始我想用 hash 来处理，但想了想，离散化不好搞，人也太多了，一不小心就hash重了，还是算了。
然后就想到了STL 的 map ：
我一开始先用 map 讲人名转化为 数字 来并查集，结果写到最后发现还得将 数字 转化为 人名 输出，得再开一个 map 。这还没啥，最主要的是我发现int转string时不好存，不好输出，只好放弃。
然后一想，没必要转化为int型并查集，直接用string并查集就完事了。
代码：
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <map> using namespace std; map <string,string> p;//思路重点 string find(string x){//直接string并查集,连fa数组都不用开 if(x!=p[x]) p[x]=find(p[x]); return p[x]; } string s,s1;//s1记录当前的father int main(){ register char ch; cin>>ch; while(ch!=‘$‘){ cin>>s; if(ch==‘#‘){ s1=s; if(p[s]=="") p[s]=s; } else if(ch==‘+‘) p[s]=s1; else cout<<s<<‘ ‘<<find(s)<<endl; cin>>ch; } return 0; }
原文：https://www.cnblogs.com/qiuchengrui/p/11012849.html