【并查集】【图论】矩形

$Link$Link

SSL 1222

$Description$Description

在一个平面上有n个矩形。每个矩形的边都平行于坐标轴并且都具有值为整数的顶点。我们用如下的方式来定义块。
 每一个矩形都是一个块。
 如果两个不同的矩形有公共线段，那么它们就组成了一个新的块来覆盖它们原来的两个块。
例子：
在图1中的矩形组成了两个不同的块。
读入矩形的个数以及它们的顶点。
找出这些矩形形成的不同的块的个数。

$Input$Input

第一行有一个整数n，1 <= n <=7000，表示矩形的个数。接下来的n行描述矩形的顶点，每个矩形用四个数来描述：左下顶点坐标(x,y)与右上顶点坐标(x,y)。每个矩形的坐标都是不超过10000的非负整数。

$Output$Output

仅有一个整数—表示由给定矩形组成的不同的块的个数。

$Sample$Sample $Input$Input

9
0 3 2 6
4 5 5 7
4 2 6 4
2 0 3 2
5 3 6 4
3 2 5 3
1 4 4 7
0 0 1 4
0 0 4 1

$Sample$Sample $Output$Output

2

$Train$Train $of$of $Thought$Thought

判断这两个矩形是否为一块，是就并查集连起来，最后求有多少个根为1的就行了

$Code$Code

#include<cstdio>
#include<iostream>
using namespace std;
int x,y,fa[7005],n,ans;
struct node
{
	int x1,y1,x2,y2;
}a[10001];
bool judge(int x,int y)
{
	if ((a[x].x1==a[y].x2 || a[x].x2==a[y].x1) && (a[x].y1==a[y].y2 || a[x].y2==a[y].y1)) return false;//只有公共点
	if (a[x].x1<=a[y].x2 && a[x].x2>=a[y].x1 && a[x].y1<=a[y].y2 && a[x].y2>=a[y].y1) return true;//有重合部位
	return false;
}
int find(int x)
{
	if (x==fa[x]) return fa[x];
	 else return fa[x]=find(fa[x]);	//寻找父节点
}
void merge(int x,int y)
{
	int xx=find(x);
	int yy=find(y);
	fa[xx]=fa[yy];//合并
}
int main()
{
	scanf("%d",&n);
	for (int i=1; i<=n; ++i) { 
		fa[i]=i;	
	    scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
	    for (int j=1; j<i; ++j)
	       if (judge(i,j)==true && fa[i]!=fa[j]) merge(i,j); 
	}
	for (int i=1; i<=n; ++i)
	 if (find(i)==i) ans++;
	printf("%d",ans); 
}