SDNUOJ1016矩形合并

传送门

题意：

给出n个矩形，把重合的矩形归成一个图形，问合并以后剩下几个图形

思路：

我开始想用dfs，但是发现不太行。

后来知道才是并查集 Orz

用一个结构体数组存矩形的左下角和右上角的坐标，再用一个一维数组来进行并查集的查找合并。

进行两层for循环，对i找i以后的矩形用不用合并，判断用不用合并的条件就是a的左下角在b右上角的左下方，a的右上角在b的左下角的右上方。

如果是需要合并，我们就找到这两个点的祖先，修改一维数组的值，最后只想要循环一遍，看看祖先是本身的有几个，即为答案。

#include<bits/stdc++.h>

using  namespace std;

#define MAX 120+5

typedef  long long ll ;

int tr[MAX], n;

struct ran

{

    int x1, y1, x2, y2;

}ar[MAX];

int judge(ran a, ran b)

{

    if(a.x1 < b.x2 && a.y1 < b.y2 && a.x2 > b.x1 && a.y2 > b.y1)

        return 1;

    else

        return 0;

}

void init()//初始化

{

    for(int i = 0; i <= n; i++)

    tr[i] = i;

}

int tfind(int x)//找爹函数

{

    if(tr[x] == x)

        return x;

    else

        return tr[x] = tfind(tr[x]);//这里是先进行的赋值操作再进行的return操作

}

void tmerge(int a, int b)//合并操作

{

    int x = tfind(a);

    int y = tfind(b);

    if(x != y)//我是采用的以左为尊的原则

        tr[y] = x;

}

int main()

{

    cin>>n;

    init();//初始化

    for(int i =  1; i <= n; i++)

    {

     cin>>ar[i].x1>>ar[i].y1>>ar[i].x2>>ar[i].y2;

    }

    for(int i = 1; i <= n; i++)

    {

        for(int j = i + 1; j <= n; j++)

        {

            if(judge(ar[i], ar[j]))

                tmerge(i, j);

        }

    }

    int ans = 0;

    for(int i = 1; i <= n; i++)

    {

        if(tr[i] == i)

            ++ans;

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

SDNUOJ1016矩形合并

题意：

思路：

最新文章

热门文章