本文共 1646 字，大约阅读时间需要 5 分钟。

菜鸟生成记(45)

思路:并查集+map<string,string>

如果把这些字符串改为数字,这一题的就非常简单,就成了一个并查集模板题了；这一题难就难在map这个数据结构的理解和使用;

—>

抓耳挠腮近一个小时完全没思路,就只知道要用并查集;同学的一个map思路点醒了我；爽！今晚可以睡个好觉了;

#include<iostream>#include<string>#include<map>#include<vector>#define son string//定义一个string的别名 #define fat string//定义一个string的别名using namespace std;map<son,fat>m;//定义一个map容器 map<son,fat>::iterator it;//map<string,string>类型的迭代器 vector<string> str1,str2,str;//定义三个容器,储存字符串 void find1(string s)//找祖先函数 {   //这就是个并查集,因为下标是字符串,所以看着有点绕;//把字符串想象成独一无二的数字下标 	string t=s,s1;	while(t!="")//m[t]==""；说明t没有父亲,即t是祖先 	{   		if(m[t]!="")		s1=m[t];//记录s的祖先 		t=m[t];	}	m[s]=s1;//这一步是并查集中的压缩路径(缩短到祖先的步数) 	//直接认祖先为父 }int main(){   	string x,t;	while(cin>>x&&x!="$")	{   		if(x[0]=='?')//要查询祖先的人 		{   			str2.push_back(x);//容器str2储存 查询祖先的人 		}		else//#和+开头的是父子关系 		{   			t=x;			t.erase(0,1);			m.insert(make_pair(t,""));//map容器<string,string> 以字符串为下标,			//开始时,每个人的父亲都为空 			str1.push_back(x);//容器str1储存 父子关系 		}		x.clear();	}	for(int i=0;i<str1.size();i++)//确定父子关系 	{   		if(str1[i][0]=='#')//#开头的人的后面+开头的人，都是#开头的儿子 		{   			string f=str1[i],t;			f.erase(0,1);//删除开头的#字符 			for(int j=i+1;j<str1.size();j++)			{   				if(str1[j][0]=='#')//再遇一个#开头的人,就是下一个爸爸了，所以结束 				break;				t=str1[j];//str1[i]的儿子 				t.erase(0,1);//删除开头的+字符 				m[t]=f;//以儿子t为下标,值储存的父亲的名字 			}		}	}	for(it=m.begin();it!=m.end();it++)	{   		find1(it->first);//寻找儿子的祖先 	}	for(int i=0;i<str2.size();i++)//查询 	{   		string t=str2[i].erase(0,1);		if(m[t]!="")//输出自己和祖先 		cout<<t<<" "<<m[t]<<endl;		else//没有父亲的，输出自己和自己(自己是自己的父亲) 		cout<<t<<" "<<t<<endl;	}	return 0;}/*#George+Rodney#Arthur+Gareth+Walter#Gareth+Edward?Edward?Walter?Rodney?Arthur$*/