DongDong认亲戚 - 并查集

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N = 1e5+10;

string s[N];
// dep 代表的是每个以i节点为根的子树的深(高)度 
int dep[N];
// i的父亲节点是 fa[i] 
int fa[N];

void init() {
  for(int i=1;i<=100000;i++) {
    fa[i]=i;
    rank[i]=1; 
  }
} 

int find(int x) {
  return x == fa[x]?x:(fa[x]=find(fa[x]));
}

void merge(int i,int j) {
  // x是i的爹 ,y是j的爹 
  int x = find(i);
  int y = find(j);
  
  //这里是判断两棵树分别的深度
  //将 深度小的树 往 深度大的树 上合并 
  //以免出现树越来高的情况 
  if(dep[x]<=dep[y]) fa[x] = y;
  else fa[y]=x;
  
  //如果两棵不同的树高度一样,那么随便谁合并谁都行,但是高度会加一(相当于加的是那个树的根) 
  if(dep[x]==dep[y] && x!=y) {
    dep[y]++;
  }
}

// map 映射一下 字符串 -> [1,n]的数字 
map<string,int>mp;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int n,m,op;
  cin>>n>>m;
  string x,y;
  
  for(int i=1;i<=n;i++) cin>>s[i],mp[s[i]]=i,fa[i]=i,dep[i]=1;
  while(m--) {
    cin>>op>>x>>y;
    if(op == 1) {
      merge(mp[x],mp[y]);
    }else {
      int i = find(mp[x]);
      int j = find(mp[y]);
      cout<<(i==j?1:0)<<endl;
    }
  }
  
  return 0;
}