1388：家谱(gen)

1. //示例代码
2. #include <iostream>
3. #include <cstdio>
4. #include <string>
5. using namespace std;
6. const int N=50005;
7. int f[N],lf;         // f为并查集，lf为当前name数组中的人数
8. string name[N],x,y;  // name数组存放每个人的名字，x和y为临时变量
9. char c;              // c为当前输入的命令类型
10. 
11. // find函数用于在name数组中查找指定名字对应的编号，如果该名字不存在则将其加入数组中并返回新的编号
12. int find(string s){
13.   for(int i=1;i<=lf;i++)
14.     if(s==name[i]) return i;
15.   name[++lf]=s;
16.   return lf;
17. }
18. 
19. // fa函数为并查集查找函数，用于查找x号元素所在集合的根节点，并进行路径压缩优化
20. int fa(int x){
21.   if(f[x]==x) return f[x];
22.   return f[x]=fa(f[x]);
23. }
24. 
25. int main(){
26. for(int i=1;i<=50000;i++) f[i]=i;  // 初始化并查集
27. while(cin>>c){
28. if(c=='$') break;
29. switch(c){
30. case '#':
31.                 cin>>x;                  // 输入父亲的名字，或者新建一个人的名字并加入name数组
32. break;
33. case '+':
34.                 cin>>y;                  // 输入儿子的名字
35. if(x!=y)f[fa(find(y))]=fa(find(x));   // 如果父亲和儿子不是同一个人，则将它们的集合合并
36. break;
37. case '?':
38.                 cin>>y;                  // 输入要查询祖先的人的名字
39.                 cout<<y<<" "<<name[fa(find(y))]<<endl;   // 输出该人的名字和最早的祖先的名字
40. break;
41.         }
42.     }
43. return 0;
44. }