记录编号	552999	评测结果	AAAAAAAAAA
题目名称	456.岛国	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.193 s
提交时间	2020-08-10 14:30:02	内存使用	4.49 MiB

#include<cstdio>
#include<algorithm>

using namespace std;
const int maxn = 5010;

int ufs[maxn];
int find(int x){
	if(x==ufs[x])return x;
	else return ufs[x]=find(ufs[x]);
}

void link(int a,int b){
	ufs[find(a)]=find(b);
}

bool linked(int a,int b){
	return find(a)==find(b);
}

struct land{
	int x1,x2,y1,y2;
}data[5010];

bool cmp(const land &a,const land &b){
	return a.x1<b.x1;
}

int ylinked(int a,int b){
	if(data[a].y1-1>data[b].y2||data[b].y1-1>data[a].y2)return -1;
	if(data[a].y1-1==data[b].y2||data[b].y1-1==data[a].y2)return 0;
	else return 1;
}

int main(){
	freopen("jx.in","r",stdin);
	freopen("jx.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++){
		ufs[i] = i;
		scanf("%d%d%d%d",&data[i].x1,&data[i].y1,&data[i].x2,&data[i].y2);
	}
	int tot=n; 
	sort(data+1,data+n+1,cmp);
	for(int i = 1;i<n;++i){
		for(int j = i+1;data[i].x2+1>=data[j].x1&&j<=n;++j){
			if(data[i].x2+1==data[j].x1){
				if(ylinked(i,j)==1&&find(i)!=find(j)){
					link(i,j);
					tot--;
				}
			}
			else {
				if(ylinked(i,j)!=-1&&find(i)!=find(j)){
					link(i,j);
					tot--;
				}
			}
		}
	}
	printf("%d",tot);
	return 0;
}