现代的人对于本家族血统越来越感兴趣。
给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
输入格式：
输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。
输出格式：
按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。
#George +Rodney #Arthur +Gareth +Walter #Gareth +Edward ?Edward ?Walter ?Rodney ?Arthur $
Edward Arthur Walter Arthur Rodney George Arthur Arthur
可以用并查集做 但是用map更加方便 注意map是没有传递性的
祖宗是自己的情况要特判
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=50005; map<string,string>mp; int main() { string fa; string s; while(cin>>s) { if(s=="$")break; if(s[0]==‘#‘) fa=s.substr(1,s.size()-1); else if(s[0]==‘+‘) { s=s.substr(1,s.size()-1); mp[s]=fa;//mp[fa]=fa; } else if(s[0]==‘?‘) { s=s.substr(1,s.size()-1); cout<<s<<" "; if(mp[s]=="") cout<<s<<endl; else { while(mp[mp[s]]!="") s=mp[s]; cout<<mp[s]<<endl; } } } }
简便一点的写法：
#include<cstdio> #include<iostream> #include<map> using namespace std; map<string,string>p; string find(string x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } string s,s1; int main() { char ch; cin>>ch; while(ch!=‘$‘) { cin>>s; if(ch==‘#‘) { s1=s; if(p[s]=="") p[s]=s; } else if(ch==‘+‘) p[s]=s1; else cout<<s<<‘ ‘<<find(s)<<endl; cin>>ch; } return 0; }
原文：https://www.cnblogs.com/bxd123/p/10832535.html
