leetcode-go/poj/1611.the-suspects/main.cc

#include <cstdio>

using namespace std;

const int N = 30000;
const int M = 500;

int n, m;

struct UF {
  int id[N];
  int sz[N];
};

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;
}

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;
    uf.sz[j] += uf.sz[i];
  } else {
    uf.id[j] = i;
    uf.sz[i] += uf.sz[j];
  }
}

int main() {
  for (;;) {
    scanf("%d %d", &n, &m);
    if (n == 0 && m == 0) break;
    for (int i = 0; i < n; i++) {
      uf.id[i] = i;
      uf.sz[i] = 1;
    }
    for (int i = 0, k, u, v; i < m; i++) {
      scanf("%d", &k);
      scanf("%d", &u);
      for (int j = 1; j < k; j++) {
        scanf("%d", &v);
        join(u, v);
      }
    }
    printf("%d\n", uf.sz[find(0)]);
  }
  return 0;
}