【题目描述】

给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

规定每个人的名字都没有空格，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。

【输入描述】

输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行；用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字，儿子的名字一定紧接着父亲的名字出现；

接下来用?name的形式表示要求该人的最早的祖先；（?name一定在父子关系描述结束之后出现）

最后用单独的一个$表示文件结束。

【输出描述】

按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

【样例输入】

#George  +Rodney  #Arthur  +Gareth  +Walter  #Gareth  +Edward  ?Edward  ?Walter  ?Rodney  ?Arthur  $

【样例输出】

Edward Arthur  Walter Arthur  Rodney George  Arthur Arthur

【题目分析】

• 首先，考点是并查集，问题的难点在于处理字符串问题，原本的并查集用的数字和数字之间的对应关系，在这个题目中变成了字符串和字符串之间的对应关系了。

• 原先并查集的指向关系是 f[2]=1，现在的并查集指向关系类似 f[tom]=jerry

• 当前的儿子有可能是别人的爸爸，当前的爸爸有可能是别人的儿子，所以，首先看看当前的这个人有没有出现过，如果没有就初始化

【参考答案一：结构体】

我们建立起结构体，用结构体的下标和结构体的属性进行关联，假设结构体定义如下：

struct people {  	string name; //存储人的名字  	int num;	//存储人的编号，用来关联名字  };

根据测试样例，我们对数据初始化应该如下：

注意：因为有上面说的“父亲和儿子有可能出现过”，所以有的名称不会两次初始化：

我们前面学过并查集的基本模板，父子之间的指向关系用 p[2]=5这种类型，在上面这种结构体中，我们用 p[i].num=p[j].num这种类型。

有一个关系从来没有变化过，也就是下标(左侧小圆圈里的数)和name的对应关系，也就是下标就是结构体中的名字属性，而结构体的num属性就是父节点。

比如，i=4, 根据并查集的知识，它的num应该是2，因为它的父节点是2。

那么，我们可以快速手动模拟出结论如下：

也就是说，我们在最后查询的时候，根据人的名字，找到对应的编号(num)，这个num，就是他祖先的下标，根据这个下标就可以找到祖先。

另外，第二点需要注意的是，我们前面学过 find函数和merge函数的优化，但是在这里需要注意，不能使用merge函数的优化，因为题目中的父子关系已经给定，不能根据秩的大小决定谁是父亲，谁是儿子。

其次，我们前面学过merge函数，我们说过，p[x]=y 和p[y]=x 对于求解关系来说都一样，不影响结果，只要保证，每次的关系都是一样即可，但是在本题中，不能这么想，本题的父子关系非常明确，一定是

p[儿子]=父亲 这种格式

【答案】

#include<bits/stdc++.h>  using namespace std;    int index=0; //用来表示结构体的数量  //定义结构体，用来存储人  struct people {  	string name; //存储人的名字  	int num;	//存储人的编号，用来关联名字  };  people p[500001];  //查找函数  int find(int n) {  	if(p[n].num==n)  		return p[n].num;  	else  		return p[n].num=find(p[n].num);    }  //合并操作  void merge(int a,int b) {  	int fa=find(a);  	int fb=find(b);  	if(fa==fb) return ;  	else   		p[fb].num=p[fa].num;  //注意此处，父子关系非常明确，一定要正确指向   	return;  }  //根据名字查找编号  int findNum(string name) {  	for(int i=0; i<index; i++) {  		if(name == p[i].name) {  			return p[i].num;  //发现名字，返回名字对应的编号  		}  	}  }  //判断遇到的人有没有在数组中出现过  bool isPeople(string name) {  	for(int i=0; i<index; i++) {  		if(p[i].name==name) {  			return true;  		}  	}  	return false;  }    int main() {  	char c; //第一个字符  	string s; //每次读入的名字  	string fatherName; // 每次读入的父亲的名字  	cin>>c;  	while(c!='$') {  		cin>>s; //读入名字  		//看看当前名名称有没有出现过，如果没有，就初始化   		if(isPeople(s)==false) {  			p[index].name=s;  			p[index].num=index;  			index++;  		}  		//#号表示 父亲，  		if(c=='#') {  			fatherName=s;  //记录下每次的父亲的名字，为下面合并做准备  		}  		// + 号表示儿子，要进行 合并操作  		if(c=='+') {  			int x = findNum(fatherName); //通过名称查找父亲的编号  			int y = findNum(s); 	//通过名称查找儿子的编号  			//如果不是同一个祖先，就合并  			if(find(x)!=find(y)) {  				merge(x,y);  			}  		}  		// ？号表示询问，查找  		if(c=='?') {  //			for(int i=0; i<index; i++) {  //				cout<<"i="<<i<<",num="<<p[i].num<<",name="<<p[i].name<<endl;  //			}		  			int num= findNum(s); //找到要查找的人的编号  			cout<<p[num].name<<endl;  		}  		cin>>c;  	}  	return 0;  }

【参考答案二：容器】

#include<map>  #include<iostream>  using namespace std;  map<string,string> father;  string getfather(string x)  {      if(father[x]!=x)      {          return getfather(father[x]);      }      else      {          return father[x];      }  }  int main()  {      char c;      string s,fat;      cin>>c;      while(c!='$')      {          cin>>s;          if(c=='#')          {              fat=s;              if(father[s]=="")    father[s]=s;          }          if(c=='+')          {              father[s]=fat;          }          if(c=='?')          {              cout<<s<<' '<<getfather(father[s])<<endl;          }          cin>>c;      }      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});