并查集的实现

#include <stdio.h>
#include <stdlib.h>

#define SWAP(a, b) { typeof(a) t = a; a = b; b = t; }

typedef enum { OK = 1, ERROR = -1 } Status;

const int N = 1E6;
int parents[N], ranks[N];

Status InitUnionFind(const int n) {
  int i;
  for (i = 1 ; i <= n; ++i) {
    *(parents + i) = i;
    *(ranks + i) = 1;
  }
  return OK;
}

// Path Compression
int Find(const int x) {
  if (*(parents + x) ^ x)
    *(parents + x) = Find(*(parents + x));
  return *(parents + x);
}

// Union by rank
void Union(int a, int b) {
  a = Find(a), b = Find(b);
  if (a == b) return;
  // a 始终指向秩小的树/集合/连通分量/簇的根或ID
  if (*(ranks + a) > *(ranks + b)) SWAP(a, b);
  
  *(parents + a) = b;
  if (*(ranks + a) == *(ranks + b))
    ++*(ranks + b);
}

int IsConnected(int a, int b) {
  return Find(a) == Find(b);
}

int main(const int argc, const char* const argv[]) {
  int n, m;
  fscanf(stdin, "%d %d", &n, &m);
  InitUnionFind(n);
  
  int op, a, b, i;
  while (m--) {
    fscanf(stdin, "%d %d %d", &op, &a, &b);
    if (op == 1) puts(IsConnected(a, b) ? "Yes" : "No");
    else         Union(a, b);
  }
  return 0;
}