leetcode-go/poj/2492.a-bugs-life/main.cc

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2000;

struct UF {
  int id[2 * N + 1];
  int sz[2 * N + 1];
} 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 S;
  scanf("%d", &S);
  for (int s = 1, n, k; s <= S; s++) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
      uf.id[i] = i;
      uf.id[i + N] = i + N;
    }
    memset(uf.sz, 0, sizeof(uf.sz));
    bool is_find = false;
    for (int i = 0, x, y; i < k; i++) {
      scanf("%d %d", &x, &y);
      if (is_find) continue;
      if (is_join(x, y)) {
        is_find = true;
        continue;
      }
      join(x, y + N);
      join(y, x + N);
    }
    if (is_find)
      printf("Scenario #%d:\nSuspicious bugs found!\n\n", s);
    else
      printf("Scenario #%d:\nNo suspicious bugs found!\n\n", s);
  }
  return 0;
}