记录编号	228678	评测结果	AAAAAAAAAA
题目名称	岛国	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.172 s
提交时间	2016-02-19 14:49:55	内存使用	0.31 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 read(){
	int x=0;char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-48;
	while(ch=getchar(),ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-48;
	return x;
}
int main(){
	freopen("jx.in","r",stdin);
	freopen("jx.out","w",stdout);
	int n;
	n=read();
	for(int i = 1;i<=n;++i){
		ufs[i]=i;
		data[i].x1=read();data[i].y1=read();data[i].x2=read();data[i].y2=read();
//		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);//之前写成了sort(data,data+n,cmp)....居然过了7个点 
	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);
	fclose(stdin);fclose(stdout);
	return 0;
}