题解 | #DongDong认亲戚#

#include<bits/stdc++.h>
using namespace std;
int n,m;
unordered_map<string,string>f;//存父节点
string find(string x){//返回x祖宗
    if(f[x]!=x)f[x]=find(f[x]);
    //将路径上的所有父节点的父节点变为祖宗(压缩)
    return f[x];
}
int main(){
    cin>>n>>m;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        f[s]=s;//初始化父节点
    }
   while(m--){
        int op;string a,b;
        cin>>op>> a>> b;
        if(op==1){
            if(a!=b) f[find(b)]=find(a);
        }
        else {
           
            if(find(a)!=find(b)) cout<<0<<endl;
            else cout<<1<<endl;
        }
    }
    
    
    
    return 0;
}