题解 | #DongDong认亲戚#

并查集 + map

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 20010;

unordered_map<string,string>fa;
int n,m;

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

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        string s;
        cin>> s;
        fa[s]=s;
    }

    while(m--){
        int op;string a,b;
        cin>>op>> a>> b;
        if(op==1){
            a=find(a),b=find(b);
            if(a!=b) fa[a]=b;
        }
        else {
            a=find(a),b=find(b);
            if(a!=b) cout<<0<<endl;
            else cout<<1<<endl;
        }
    }
    return 0;
}