#include #include typedef struct { int p, rank; } UnionFind; void init_uf(UnionFind *uf, int n) { int i; for (i = 0; i < n; i++) { uf[i].p = i; uf[i].rank = 0; } } int find(UnionFind *uf, int n, int x) { if (uf[x].p != x) { uf[x].p = find(uf, n, uf[x].p); } return uf[x].p; } void merge(UnionFind *uf, int n, int x, int y) { int res1, res2; res1 = find(uf, n, x); res2 = find(uf, n, y); if (res1 != res2) { if (uf[res1].rank > uf[res2].rank) { uf[res2].p = res1; } else { uf[res1].p = res2; if (uf[res1].rank == uf[res2].rank) { uf[res2].rank++; } } } } #define MAX_DIM 30 #define MAX_CELL (MAX_DIM*MAX_DIM*MAX_DIM) #define MAX_P 20 typedef struct { int p, cell[MAX_P]; } Monarchy; void process_adj(Monarchy monarchy, int mon_index, int galaxy[MAX_CELL], UnionFind *uf, int m, int n, int k, int l) { int i, c, x, y, z; for (i = 0; i < monarchy.p; i++) { c = monarchy.cell[i]; x = (c % (n*m)) % n; y = (c % (n*m)) / n; z = c / (n*m); /* top and bottom */ if (z < k-1 && galaxy[c+n*m] >= 0) { merge(uf, l, mon_index, galaxy[c+n*m]); } if (z > 0 && galaxy[c-n*m] >= 0) { merge(uf, l, mon_index, galaxy[c-n*m]); } /* front and back */ if (y < m-1 && galaxy[c+n] >= 0) { merge(uf, l, mon_index, galaxy[c+n]); } if (y > 0 && galaxy[c-n] >= 0) { merge(uf, l, mon_index, galaxy[c-n]); } /* left and right */ if (x < n-1 && galaxy[c+1] >= 0) { merge(uf, l, mon_index, galaxy[c+1]); } if (x > 0 && galaxy[c-1] >= 0) { merge(uf, l, mon_index, galaxy[c-1]); } galaxy[c] = mon_index; } } int main(void) { int num, n, m, k, l; Monarchy monarchy[MAX_CELL]; int galaxy[MAX_CELL]; UnionFind uf[MAX_CELL]; int comp[MAX_CELL]; char mark[MAX_CELL]; int num_comp; int months, connected; int i, j, p; scanf("%d", &num); while (num-- > 0) { /* read input */ scanf("%d %d %d %d\n", &n, &m, &k, &l); for (i = 0; i < l; i++) { scanf("%d", &(monarchy[i].p)); for (j = 0; j < monarchy[i].p; j++) { scanf("%d", &(monarchy[i].cell[j])); } } /* initialize */ for (i = 0; i < n*m*k; i++) { galaxy[i] = -1; } init_uf(uf, l); months = 0; num_comp = 0; /* now process backwards in time */ for (i = l-1; i >= 0; i--) { process_adj(monarchy[i], i, galaxy, uf, m, n, k, l); comp[num_comp++] = i; memset(mark, 0, num_comp); for (j = 0; j < num_comp-1; j++) { if (find(uf, l, comp[j]) == find(uf, l, i)) { mark[j] = 1; } } for (j = p = 0; j < num_comp; j++) { if (!mark[j]) { comp[p++] = comp[j]; } } num_comp = p; if (num_comp > 1) { months++; } } printf("%d\n", months); } return 0; }