SDNU 1016.矩形合并

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6;
#define ll long long
int sign[1000+8], v[1000+8];
int n;
struct node
{
    int lx, ly, rx, ry;
} root[1000+8];
int get(int x)
{
    if(x != sign[x])
    {
        sign[x] = get(sign[x]);
    }
    return sign[x];
}
int bcj(int x, int y)//判断他们是不是同一个祖先
{
    int miao = get(x), ying = get(y);
    if(miao != ying)//如果还不是同一个祖先，就把他们并在一起
    {
        sign[miao] = ying;
        return 1;
    }
    return 0;
}
int unio(node a, node b)//合并矩阵
{
    if(a.lx >= b.rx || a.ly >= b.ry)
        return 0;
    if(a.rx <= b.lx || a.ry <= b.ly)
        return 0;
    return 1;
}
int main()
{
    int sum = 0;
    while(~scanf("%d", &n) && n)
    {
        fill(v, v+1000+8, 0);
        for(int i = 0; i<n; i++)
        {
            sign[i] = i;
            scanf("%d%d%d%d", &root[i].lx, &root[i].ly, &root[i].rx, &root[i].ry);
        }
        for(int i = 0; i<n; i++)
        {
            for(int j = i+1; j<n; j++)
            {
                if(unio(root[i], root[j]))//如果他们是同一个矩阵
                    bcj(i, j);//合并这两玩意儿
            }
        }
        for(int i = 0; i<n; i++)
            v[get(i)] = 1;//如果该矩阵已经被合并，就标记一下（记录他们最后指向的那个矩阵）
        for(int i = 0; i<n; i++)
            if(v[i] == 1)//如果那个矩阵（最后指向的那个矩阵）被标记了，就++
                sum++;
        printf("%d\n", sum);
    }
    return 0;
}