代码：

#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
map<int,string>mp2;
string ns,fs;
int father[50050],cnt;
int find(int m) {
	if(father[m]!=m)
		father[m]=find(father[m]);
	return father[m];
}
void join(int a,int b) {
	int fa=find(a),fb=find(b);
	if(fa!=fb) {
		father[fb]=fa;
	}
}
int main() {
	for(int i=0;i<50050;i++)
		father[i]=i;
	while(1) {
		getline(cin,ns);
		if(ns[0]=='#') {
			fs=ns.substr(1);
			mp.insert(pair<string,int>(fs,++cnt) );
			mp2.insert(pair<int,string>(cnt,fs));
		} else if(ns[0]=='+') {
			ns=ns.substr(1);
			mp.insert(pair<string,int>(ns,++cnt));
			mp2.insert(pair<int ,string>(cnt,ns));
			join(mp[fs],mp[ns]);
		} else if(ns[0]=='?') {
			ns=ns.substr(1);
			cout<<ns<<" "<<mp2[find(mp[ns])]<<endl;
		} else if(ns[0]=='$')break;
	}
	return 0;
}

思路：运用并差集+map将父亲和孩子合并，以此找到真正的祖先。