题解 | #DongDong认亲戚#

并查集模板题

#include <bits/stdc++.h>
using namespace std;
int fa[20020];
map<string,int> m1;
int n,m;
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);    //路径压缩
}
void Merge(int x,int y){
    fa[find(x)] = find(y);    //令x的父亲等于y的父亲
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        string str;
        cin>>str;
        m1[str] = i;
        fa[i] = i;
    }
    while(m--){
        int num;
        string s1,s2;
        cin>>num>>s1>>s2;
        if(num == 1) Merge(m1[s1],m1[s2]);
        else{
            if(find(m1[s1]) != find(m1[s2])) cout<<0<<'\n';
            else cout<<1<<'\n';
        }
    }
    return 0;
}