记录编号	228664	评测结果	AAAAAAAAAA
题目名称	456.岛国	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.206 s
提交时间	2016-02-19 14:29:17	内存使用	0.38 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;  ///-1:no link 1:link 0:???
	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);
	}
	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)link(i,j);
			}
			else {
				if(ylinked(i,j)!=-1)link(i,j);
			}
		}
	}
	int tot=0;
	for(int i = 1;i<=n;++i){
		if(find(i)==i)tot++;
	}
	printf("%d",tot);
	fclose(stdin);fclose(stdout);
}