sdnu 1016.矩形合并 (并查集)

Description

平面上有n个矩形，给定每个矩形的左下角坐标和右上角坐标。如果把重合的矩形合并成一个图形，则经过合并之后，还剩多少个图形？

Input

第1行：一个整数n(1 <= n <= 100)，表示矩形的数量。
第2至第n+1行：每行有4个整数(不会超过int)，第i 行中的4个数字分别表示编号为i-1的矩形的左下角x、y坐标与右上角x、y坐标。

Output

合并后剩余的图形数。

Sample Input

3
0 0 2 2
1 1 4 4
4 4 5 5

Sample Output

2

Hint

相邻不重合的图形不合并

Source

SDNU ACM-ICPC 2010复赛(2009级)

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=120;
struct node
{
    int x1,x2,y1,y2;
}s[N];
int a[120];
bool judge(node a,node b)
{
    if(a.x1<b.x2&&a.y1<b.y2&&a.x2>b.x1&&a.y2>b.y1)
        return 1;
    return 0;
}
int Find(int x)
{
    if(a[x]!=x)
    {
        a[x]=Find(a[x]);
    }
    return a[x];
}
void unionn(int x,int y)
{
    int xx=Find(x);
    int yy=Find(y);
    if(xx!=yy)
    {
        a[xx]=yy;
    }
}

//int Find(int x){return fa[x] == x ? x : fa[x] = Find(fa[x]);}
//void unionn(int x, int y){fa[Find(x)] = fa[Find(y)];}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            a[i]=i;
        for(int i=1;i<=n;i++)
            scanf("%d%d%d%d",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2);
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(judge(s[i],s[j]))
                {
                    unionn(i,j);
                }
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==i)
                ++cnt;
        }
        cout<<cnt<<'\n';
    }
    return 0;
}