SSL 1222_矩形_并差集

发布于 2019-04-26  887 次阅读


题目描述

给出n个矩形,求不向交的矩形块有多少个

思路

判断一下每一个矩形是否相交,如果相交的话就合并两个集合,最后判断一下数组中有几个数为0就可以了
O(n^2)

#include 
struct arr
{
    int x1,x2,y1,y2;
};
arr a[100001];
int f[100001];
int find(int x)
{
    if (!f[x]) return x;
    f[x]=find(f[x]);
    return f[x];
}
int insert(int x,int y)
{
    if (find(x)!=find(y))
    {
        f[find(x)]=find(y);
        return 1;
    }
    return 0;
}
int xx(int x,int y)
{
    if (a[x].x1>a[y].x2||a[x].x2a[y].y2||a[x].y2
]]>