題意：
一個帝國有N個國家組成，每個國家包括N
i個區(qū)域（一個小方格），然后第i個國家在第i月會分離出去。問有多少個月帝國仍然是一個整體。
PS：說道帝國，就想到黃金雄教授在ICPC開幕式上用閩南語講的（。。。ACM大帝國。。），那發(fā)音，拿語言的組織都超級搞笑
思路：
并查集，逆向思維。最后所有的國家應(yīng)該都是獨(dú)立的。相當(dāng)于一個國家一個國家逐月的聯(lián)合起來。用并查集統(tǒng)計是否當(dāng)前集合為一個整體即可。暴力的方法沒實(shí)驗(yàn)過，不過復(fù)雜度會高達(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 }