leetcode-go/written-exam/kickstart-2019-E/no1/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

#define N_MAX 100000

struct UF {
  int id[N_MAX + 1];
  int sz[N_MAX + 1];
  int n;

  void Init(int n) {
    memset(sz, 0, sizeof(sz));
    for (int i = 0; i <= n; i++) id[i] = i;
  }

  int Find(int i) {
    int j = id[i];
    if (i == j) return i;
    j = Find(j);
    id[i] = j;
    return j;
  }

  bool Union(int i, int j) {
    i = Find(i);
    j = Find(j);
    if (i == j) return false;
    if (sz[i] < sz[j]) {
      id[i] = j;
    } else {
      if (sz[i] == sz[j]) sz[i]++;
      id[j] = i;
    }
    return true;
  };
} uf;

struct Pair {
  int x;
  int y;

  bool operator<(const Pair &that) const {
    if (this->x != that.x) return this->x < that.x;
    return this->y < that.y;
  };
};

int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, M;
    scanf("%d %d", &N, &M);
    uf.Init(N);
    set<Pair> black;
    for (int i = 0, C, D; i < M; i++) {
      scanf("%d %d", &C, &D);
      if (C < D) black.insert(Pair{C, D});
      else black.insert(Pair{D, C});
    }
    int sugar = 0;
    set<Pair>::iterator it;
    for (it = black.begin(); it != black.end(); ++it)
      if (uf.Union(it->x, it->y)) sugar++;
    for (int i = 1; i < N; i++)
      for (int j = i + 1; j <= N; j++)
        if (uf.Union(i, j)) sugar += 2;
    printf("Case #%d: %d\n", t, sugar);
  }
  return 0;
}