【题目描述】

给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
规定每个人的名字都没有空格，且没有任意两个人的名字相同。最多可能有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;
}