Submission #1519390

---

Source Code Expand

#include <cstdio>

#define MAX_N 100000

int par[MAX_N], rank[MAX_N];
int n, q;

void init(){
  for(int i = 0; i < n; i++)
    par[i] = i;
}

int find(int x){
  if(par[x] == x)
    return x;
  else
    return find(par[x]);
}

void unite(int x, int y){
  x = find(x);
  y = find(y);

  if(x == y)
    return;

  if(rank[x] > rank[y]){
    par[y] = x;
  }else{
    par[x] = y;
    if(rank[x] == rank[y]){
      rank[y]++;
    }
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

int main(){
  int P, X, Y;
  scanf("%d %d", &n, &q);

  init();

  for(int i = 0; i < q; i++){
    scanf("%d %d %d", &P, &X, &Y);
    X--; Y--;    
    if(!P){
      unite(X, Y);
    }else{
      if(same(X, Y)){
        printf("Yes\n");
      }else{
        printf("No\n");
      }
    }
  }
  return 0;
}

Submission Info

Judge Result