並查集練習題 島國 jx 題解

【題目描述】
很久很久很久很久很久很久以前......

有一個島國。

這個國家的領地是一塊座標從(1,1)到(K,K)的正方形（包括領海和領陸，座標(x,y)是指(x,y)這塊土地，並非一個點）

衛星資訊會告訴你這個國家的土地情況，希望你能根據給出的資訊計算出這個國家有多少個島。

衛星給出的資訊形如x1 y1 x2 y2，表示左下角座標為x1,y1,右上角座標為x2,y2的這一個矩形區域是陸地

輸入格式：

第一行一個整數n，表示衛星會傳送給你n條資訊

下面n行每行有4個整數，x1,y1,x2,y2，含義如上

輸出格式：

第一行，一個整數Sum，表示這個國家的島的數量

注，只有一個公共點的兩塊陸地不算是一塊區域，具體如樣例

樣例輸入：

3

1 1 2 2

1 3 1 3

3 3 4 5

樣例輸出：

2

樣例解釋：

0 0 1 1 0

0 0 1 1 0

1 0 1 1 0

1 1 0 0 0

1 1 0 0 0

（1是陸地，0是海）

資料規模：

對於30%的資料，K<=1000，n<=100

對於100%的資料，K<=20000，n<=5000，x1<=x2，y1<=y2，1<=x1,x2,y1,y2<=K

by pom

【分析】

先緩存每個矩形的兩個點的坐標，然後弄個O(N^2)的枚舉，枚舉任意兩個矩形是否同屬一個島嶼，如果是，則Merge Them，這就用到並查集了。

最後，判斷有幾個獨立的集合集合。

PS。我差點把這題寫成“矩形分割”一類的了～ORZ～

【我的代碼】

 裸代碼RawCode

C++语言: Codee#25690

01 /*
02 *Problem: 島國
03 *Author: Yee-fan Zhu
04 *Thanks: KingFree
05 *Website: zhuyf.tk
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 using namespace std;
10 const int MAXN=5002;
11 int UFS[MAXN];
12 int N;
13 int Flag[MAXN];
14 class Point
15 {public: int x1,x2,y1,y2;}P[MAXN];
16
17 int UFS_Find(int x)
18 {
19     int t,p; p=x;
20     while(UFS[p]!=p) p=UFS[p];
21     while(UFS[x]!=x)
22     {t=UFS[x]; UFS[x]=p;x=t;}
23     return p;
24 }
25
26 bool UFS_Check(int a,int b)
27 { return (UFS_Find(a)==UFS_Find(b)); }
28
29 void UFS_Merge(int a,int b)
30 { UFS[UFS_Find(b)]=UFS_Find(a); }
31
32 void init()
33 {
34     scanf("%d\n",&N);
35     for(int i=1;i<=N;i++)
36         scanf("%d %d %d %d\n",&P[i].x1,&P[i].y1,&P[i].x2,&P[i].y2);
37     for(int i=1;i<=N;i++)
38         UFS[i]=i,Flag[i]=0;
39 }
40
41 void solve()
42 {
43     for(int i=1;i<=N;i++)
44     {
45         for(int j=i+1;j<=N;j++)
46         {
47             if(UFS_Check(i,j)) continue;
48             /*四邊相離*/
49             if(P[i].x1>P[j].x2+1) continue;
50             if(P[i].x2<P[j].x1-1) continue;
51             if(P[i].y1>P[j].y2+1) continue;
52             if(P[i].y2<P[j].y1-1) continue;
53             /*四角相接*/
54             if(P[i].x1==P[j].x2+1 && P[i].y2+1==P[j].y1) continue;
55             if(P[i].x1==P[j].x2+1 && P[i].y1-1==P[j].y2) continue;
56             if(P[i].x2+1==P[j].x1 && P[i].y2+1==P[j].y1) continue;
57             if(P[i].x2+1==P[j].x1 && P[i].y1-1==P[j].y2) continue;
58             UFS_Merge(i,j);
59         }
60     }
61     int Ans=0;
62     for(int i=1;i<=N;i++)
63     {
64         if(Flag[UFS_Find(i)]==0)
65         {
66             Ans++;
67             Flag[UFS_Find(i)]=1;
68         }
69     }
70     printf("%d\n",Ans);
71 }
72
73 int main()
74 {
75     freopen("jx.in","r",stdin);
76     freopen("jx.out","w",stdout);
77     init();
78     solve();
79     return 0;
80 }