最原始代码，非并查集：

#include <bits/stdc++.h>
using namespace std;
// fa[x] 表示 x 的直接父亲是谁
// 如果 fa[x] == x，说明 x 没有父亲记录，是祖先
map<string,string> fa;
// 找到 x 的最早祖先（最原始写法）
// 思想：一直沿着“父亲指针”往上走，直到不能再走
string getrt(string x){
    // 如果这个人从未出现过，先把他当作一个独立的人
    if(!fa.count(x)) fa[x]=x;
    // 一直向上找父亲
    while(fa[x]!=x){
        x=fa[x];
    }
    // 走到这里时，x 就是最早祖先
    return x;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    string s;string par; // 当前正在描述的父亲
    string son,ask; // 儿子string ask; // 查询的人
    // 按顺序读取所有指令，直到读到 $
    while((cin>>s) && s!="$"){
        // #name ：声明一个父亲
        if(s[0]=='#'){
            par=s.substr(1);
            // 如果这个父亲第一次出现，让他指向自己
            if(!fa.count(par)){
                fa[par]=par;
            }
        }else if(s[0]=='+'){  // +name ：说明这是刚才父亲的儿子
            son=s.substr(1);
            // 找到父亲所在家族的最早祖先
            string rt=getrt(par);
            // 题目保证每个人至多一个父亲
            // 所以儿子可以直接认这个祖先作为自己的父亲链源头
            fa[son]=rt;
        }else if(s[0]=='?'){ // ?name ：查询最早祖先
            ask=s.substr(1);
            // 顺着父亲指针一路往上找
            string rt=getrt(ask);
            // 按题目要求输出
            cout<<ask<<" "<<rt<<"\n";
        }
    }
    return 0;
}

不带压缩的：

#include <bits/stdc++.h>
using namespace std;
map<string,string> fa;
string find0(string x){
    if(!fa.count(x)) fa[x]=x;
    while(fa[x]!=x) x=fa[x]; // 最原始：沿父亲指针一路向上找根
    return x;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s,par,son,ask;
    while((cin>>s) && s!="$"){
        if(s[0]=='#'){
            par=s.substr(1);
            if(!fa.count(par)) fa[par]=par;
        }else if(s[0]=='+'){
            son=s.substr(1);
            string rt=find0(par); // 父亲所在家族的最早祖先
            fa[son]=rt; // 由于每人至多一个父亲，直接挂到祖先即可
        }else if(s[0]=='?'){
            ask=s.substr(1);
            string rt=find0(ask); // 查询最早祖先
            cout<<ask<<" "<<rt<<"\n";
        }
    }
    return 0;
}

带路径压缩的：

#include <bits/stdc++.h>
using namespace std;
map<string,string> fa;
string find(string x){
    if(!fa.count(x)) fa[x]=x;
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s,par,son,ask;
    while((cin>>s) && s!="$"){
        if(s[0]=='#'){
            par=s.substr(1);
            if(!fa.count(par)) fa[par]=par;
        }else if(s[0]=='+'){
            son=s.substr(1);
            string rt=find(par); // 路径压缩，拿到当前父亲所在家族的“最早祖先”
            fa[son]=rt; // 儿子直接指向该祖先（等价于并到同一集合）
        }else if(s[0]=='?'){
            ask=s.substr(1);
            string rt=find(ask); // 查询时压缩路径，rt 就是最早祖先
            cout<<ask<<" "<<rt<<"\n";
        }
    }
    return 0;
}