leetcode-go/poj/1182.food-chain/main.cc

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 50000;

struct UF {
  int id[3 * N + 1];
  int sz[3 * N + 1];
};

UF uf;

int find(int i) {
  if (i == uf.id[i]) return i;
  int j = find(uf.id[i]);
  uf.id[i] = j;
  return j;
}

bool is_join(int i, int j) { return find(i) == find(j); }

void join(int i, int j) {
  i = find(i);
  j = find(j);
  if (i == j) return;
  if (uf.sz[i] < uf.sz[j]) {
    uf.id[i] = j;
  } else {
    if (uf.sz[i] == uf.sz[j]) uf.sz[i]++;
    uf.id[j] = i;
  }
}

int main() {
  int n, k, d, x, y;
  scanf("%d %d", &n, &k);
  memset(uf.sz, 0, sizeof(uf.sz));
  for (int i = 1; i <= n; i++) {
    uf.id[i] = i;
    uf.id[i + N] = i + N;
    uf.id[i + 2 * N] = i + 2 * N;
  }
  int ans = 0;
  for (int i = 0; i < k; i++) {
    scanf("%d %d %d", &d, &x, &y);
    if (x < 1 || n < x || y < 1 || n < y) {
      ans++;
      continue;
    }
    if (d == 1) {
      if (is_join(x, y + N) || is_join(x, y + 2 * N)) {
        ans++;
        continue;
      }
      join(x, y);
      join(x + N, y + N);
      join(x + 2 * N, y + 2 * N);
    } else {
      if (is_join(x, y) || is_join(x, y + 2 * N)) {
        ans++;
        continue;
      }
      join(x, y + N);
      join(x + N, y + 2 * N);
      join(x + 2 * N, y);
    }
  }
  printf("%d\n", ans);
  return 0;
}