学步园

题目描述
        现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
输入格式
       输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。
输出
      按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。
样例输入
#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$
样例输出
Edward Arthur
Walter Arthur
Rodney George

Arthur Arthur

数据与题解

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
string s[50010];
int father[50010];
int len;
int find(string,int );
int getfather(int);
void work();
int main()
{
	//freopen("gen7.in","r",stdin);
	//freopen("gen.out","w",stdout);
	work();
	return 0;
}
void work()
{
	memset(father,0,sizeof(father));
	string s1,s2,name1,name2;
	int k1,k2;//k1记录上一次读入名字在数组中的位置，k2为当前名字 
	len++;//len记录存储名字的数组长度 
	cin>>s1;//读第一个名字直接放在数组中 
	if(s1[0]=='$') return;
	s[len]=s1.substr(1,6);//取出名字 
	name1=s[len];
	k1=len;	
	while(1)
	{			
		cin>>s2;//读当前字符 
		//cout<<s2<<endl;
		if(s2[0]=='$')break;//如果当前字符第一个字符为$则结束循环 
		name2=s2.substr(1,6);//取出名字 
		k2=find(name2,len);//找到名字在数组中的位置，为0表示没有 
		if(s2[0]=='?')//遇到？直接找到其祖先，并输出 
		{
			cout<<name2<<' '<<s[getfather(k2)]<<endl;
			continue;//输出后不需要进行下面的操作， 
		}
		if(k2==0)//当k2==0表示名字没有出现过，加入数组 
		{
			len++;
			s[len]=name2;
			k2=len;//这个很重要，容易忽视 
		}
		if(s2[0]=='+') father[k2]=k1;//+表明其有父亲节点，为上一个输入 
		name1=name2;//把当前输入记录到k1中，以备下次用 
		k1=k2;		
	}
}
int find(string s1,int len)
{
	for(int i=1;i<=len;i++)
	{
		if(s1==s[i]) return i;
	}
	return 0;
}
int getfather(int x)
{
	if(x==0)return 0;
	if(father[x]==0) return x;
	father[x]=getfather(father[x]);
	return father[x];
}