P2814 家谱（map + 并查集）

题目描述

代码

#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+50; int n,m; char ch; string fname,sname,s; map<string,string>mp; //mp[儿子，父亲]; string find(string s){ //寻找祖先 if(s == mp[s]) return s; else{ string F = find(mp[s]); mp[s] = F; return F; } } int main(){ //freopen("a.txt","r",stdin); while(cin>>ch){ cin>>s; if(ch == '+'){ mp[s] = fname; } else if(ch == '#'){ fname = s; if(mp[fname] == ""){ mp[fname] = fname; } } else if(ch == '?'){ cout<<s<<' '<<find(s)<<endl; } else{ break; } } return 0; }