源程序名 GEN.???(PAS,C,CPP)
可执行文件名 GEN.EXE
输入文件名 GEN.IN
输出文件名 GEN.OUT
时间限制 2S
现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
输入
输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。
输出
按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。
样例
GEN.IN
#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$
GEN.OUT
Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur
code:
#include<fstream>
#include<string>
using namespace std;
struct node
{
int sn;
string name;
struct node *next;
};
node *g[127]={0};
int pn=0,a[50001];
string name[50001];
int find(string s)
{
node *p;
p=g[s[0]];
while (p)
{
if (p->name==s) return p->sn;
p=p->next;
}
name[++pn]=s;
p=new node;
p->name=s;
p->sn=pn;
p->next=g[s[0]];
g[s[0]]=p;
return pn;
}
int f(int x)
{
while (a[x]!=x) x=a[x];
return x;
}
ifstream cin("gen.in");
ofstream cout("gen.out");
int main()
{
for (int i=1;i<=50000;i++) a[i]=i;
char ch;
string s1,s2;
int x,y,k1,k2;
cin>>ch;
while (ch!='?')
{
cin>>s1;
x=find(s1);
k1=f(x);
a[x]=k1;
cin>>ch;
while (ch=='+')
{
cin>>s2;
y=find(s2);
k2=f(y);
a[k2]=a[y]=k1;
cin>>ch;
}
}
while (ch!='$')
{
cin>>s1;
cout<<s1<<" "<<name[f(find(s1))]<<endl;
cin>>ch;
}
system("pause");
return 0;
}
posted on 2011-11-01 15:47
龙在江湖 阅读(515)
评论(0) 编辑 收藏 引用 所属分类:
算法