題意：
一個(gè)帝國(guó)有N個(gè)國(guó)家組成，每個(gè)國(guó)家包括N
i個(gè)區(qū)域（一個(gè)小方格），然后第i個(gè)國(guó)家在第i月會(huì)分離出去。問(wèn)有多少個(gè)月帝國(guó)仍然是一個(gè)整體。
PS：說(shuō)道帝國(guó)，就想到黃金雄教授在ICPC開幕式上用閩南語(yǔ)講的（。。。ACM大帝國(guó)。。），那發(fā)音，拿語(yǔ)言的組織都超級(jí)搞笑
思路：
并查集，逆向思維。最后所有的國(guó)家應(yīng)該都是獨(dú)立的。相當(dāng)于一個(gè)國(guó)家一個(gè)國(guó)家逐月的聯(lián)合起來(lái)。用并查集統(tǒng)計(jì)是否當(dāng)前集合為一個(gè)整體即可。暴力的方法沒實(shí)驗(yàn)過(guò)，不過(guò)復(fù)雜度會(huì)高達(dá)30^6，(*^__^*) 嘻嘻……，RP好的可以去拼一下～
代碼：
1 //============================================================================
2 // Name : pku1235.cpp
3 // Author : yzhw
4 // Version :
5 // Copyright : yzhw
6 // Description : Hello World in C++, Ansi-style
7 //============================================================================
8
9 #include <iostream>
10 #include <cstdio>
11 #include <vector>
12 #include <algorithm>
13 using namespace std;
14 # define LEFT (data[i][j]%(n*m))
15 int set[30000],n,m,k,l,data[30000][21];
16 bool used[30000];
17 int find(int pos)
18 {
19 if(set[pos]==pos) return pos;
20 else return set[pos]=find(set[pos]);
21 }
22 int main() {
23 int testcase;
24 scanf("%d",&testcase);
25 while(testcase--)
26 {
27 scanf("%d%d%d%d",&n,&m,&k,&l);
28 int total=0,ans=0,c;
29 for(int i=0;i<n*m*k;i++)
30 set[i]=i,used[i]=false;
31 for(int i=0;i<l;i++)
32 {
33 scanf("%d",&data[i][0]);
34 for(int j=1;j<=data[i][0];j++)
35 scanf("%d",&data[i][j]);
36 }
37 for(int i=l-1;i>=0;i--)
38 {
39 c=0;
40 for(int j=1;j<=data[i][0];j++)
41 {
42 vector<int> refer;
43 if(data[i][j]-n*m>=0&&used[data[i][j]-n*m]) refer.push_back(find(data[i][j]-n*m));
44 if(data[i][j]+n*m<n*m*k&&used[data[i][j]+n*m]) refer.push_back(find(data[i][j]+n*m));
45 if(LEFT%n!=0&&used[data[i][j]-1]) refer.push_back(find(data[i][j]-1));
46 if(LEFT%n!=n-1&&used[data[i][j]+1]) refer.push_back(find(data[i][j]+1));
47 if(LEFT/n!=0&&used[data[i][j]-n]) refer.push_back(find(data[i][j]-n));
48 if(LEFT/n!=m-1&&used[data[i][j]+n]) refer.push_back(find(data[i][j]+n));
49 sort(refer.begin(),refer.end());
50 vector<int>::iterator end=unique(refer.begin(),refer.end());
51 c+=end-refer.begin();
52 for(int t=0;t<end-refer.begin();t++)
53 set[find(refer[t])]=find(data[i][j]);
54 used[data[i][j]]=true;
55 }
56 total=total+data[i][0]-c;
57 if(total==1) ans++;
58 }
59 printf("%d\n",l-ans);
60 }
61 return 0;
62 }