题解 | #DongDong认亲戚#

并查集AC代码+注释如下：

#include<bits/stdc++.h>
using namespace std;
int p[20005];
int get(int x){return p[x]==x?x:p[x]=get(p[x]);}//查询
void merge(int x,int y){p[get(x)]=get(y);}//合并
map<string,int>mp;//映射
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){//输入
        string t;cin>>t;
        mp[t]=i;
    }
    for(int i=1;i<=n;i++)p[i]=i;//并查集初始化
    while(m--){
        int op;string s1,s2;cin>>op>>s1>>s2;
        if(op==1)merge(mp[s1],mp[s2]);//1
        else cout<<(get(mp[s1])==get(mp[s2]))<<'\n';//2
    }   
}