好像基于哈希表的unoedered_map快一点。。。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

unordered_map<string,string> p;

string find(string x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}

void merge(string x,string y)
{
	p[y] = find(x);
}

int main()
{
	char ch = getchar();
	string a,b;
	while(ch!='$')
	{
		if(ch == '#')
		{
			cin >> a;
			//cout << p[a] << endl;
			if(p[a] == "") p[a] = a;
		}
		if(ch == '+')
		{
			cin >> b;
			merge(a,b);
		}
		if(ch == '?')
		{
			string t;
			cin >> t;
			cout << t << " " << find(t) << endl;
		}
		ch = getchar();
	}
	return 0;
}

普通并查集，但是由于为字符串，所以用map存储关系

注意merge时并非将 本人的祖先与祖先合并!

#include <bits/stdc++.h>
#define int long long int

using namespace std;

const int N = 1e5 + 7;
map<string,string> bond;
string s1,s; 

string get(string x){
    if(bond[x] == x)return x;
    return bond[x] = get(bond[x]);
}

void merge(string x,string y){
    y = get(y);
    bond[x] = y;
}

signed main(){
    char ch = getchar();
    while(ch != '$'){
    if(ch == '#'){
        cin >> s;
        if(bond[s] == "")bond[s] = s;
    }
    if(ch == '+'){
        cin >> s1;
        merge(s1,s); 
    }
    if(ch == '?'){
        cin >> s;
        get(s);//更新祖先确保最早
        cout << s << " " << bond[s] << endl;
    }
        ch = getchar();
    }
    return 0;
}