家谱

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];
}

家谱,布布扣,bubuko.com

家谱

原文：http://blog.csdn.net/hbhszxyb/article/details/21084033