/* solution to galactic breakup Bob Roos */ #include int instances; int n,m,k; /* n by m by k cube */ int l; /* l monarchies */ int p[27000]; /* number of dominions in each monarchy */ int parent[27000]; /* union/find data structure */ int wt[27000]; /* weight of each tree in the union/find structure */ int dom[27000][20]; /* dominions in each monarchy */ int find(int a) { int i,j; if (parent[a] == -1) /* base case: a is the root */ return a; if (parent[a] == -2) /* base case: a not used yet */ return -2; i = parent[a]; /* a is NOT the root; get its parent */ j = parent[i]; /* get a's grandparent (if any) */ while (j >= 0) /* while a has a grandparent... */ { parent[a] = j; /* replace a's parent with a's grandparent */ wt[i] -= wt[a]; /* reduce weight of a's old parent */ a = i; /* move up the tree ...*/ i = j; j = parent[j]; } return i; } int yunion(int a, int b) { int left = find(a); int right = find(b); if (left == right) return 0; /* nothing to do; no change in number of components */ if (wt[left] >= wt[right]) { parent[right] = left; wt[left] += wt[right]; } else { parent[left] = right; wt[right] += wt[left]; } return -1; } void nbrs(int d, int *numroots) { int adj, incr, r, c, t; r = d%n; /* cube row of d */ c = (d/n)%m; /* cube column of d */ t = (d/n/m)%k; /* cube tier of d */ for (incr = -1; incr <= 1; incr += 2) { if (r+incr >= 0 && r+incr < n) { adj = r+incr + c*n + t*n*m; if (find(adj) > -2) { *numroots += yunion(d,adj); /* printf("%d is adjacent to %d\n",d,adj); */ } } if (c+incr >= 0 && c+incr < m) { adj = r + (c+incr)*n + t*n*m; if (find(adj) > -2) { *numroots += yunion(d,adj); /* printf("%d is adjacent to %d\n",d,adj); */ } } if (t+incr >= 0 && t+incr < k) { adj = r + c*n + (t+incr)*n*m; if (find(adj) > -2) { *numroots += yunion(d,adj); /* printf("%d is adjacent to %d\n",d,adj); */ } } } } int disconn() { int numroots = 0; /* number of roots in the union/find forest */ int count = 0; /* number of months in which empire is disconn. */ int mon, i, d; for (i = 0; i < n*m*k; i++) { parent[i] = -2; /* -2 denotes an unprocessed dominion */ wt[i] = 1; /* weight of union/find tree rooted at i */ } /* Loop through monarchies in reverse order of secession and "un-secede" them, adding their dominions to the empire until the whole empire has been restored. */ for (mon = l-1; mon >= 0; mon--) { /* loop through each dominion in the monarchy */ for (i = 0; i < p[mon]; i++) { d = dom[mon][i]; /* printf("adding dominion %d: ",d); */ parent[d] = -1; /* -1 means this is a root of a union/find tree */ numroots++; /* for now, anyway ...*/ nbrs(d,&numroots); /* process neighbors of d */ } /* See if empire is disconnected now: */ if (numroots > 1) count++; /* increment number of disconnected months */ } return count; } int main() { int i,j,inst; scanf("%d",&instances); for (inst = 0; inst < instances; inst++) { // while (scanf("%d %d %d %d", &n, &m, &k, &l) && n > 0) scanf("%d %d %d %d", &n, &m, &k, &l); for (i = 0; i < l; i++) { scanf("%d",&p[i]); for (j = 0; j < p[i]; j++) scanf("%d",&dom[i][j]); } printf("%d\n",disconn()); } }