hdu - 4619 - Warm up 2

題意：1x2的骨牌蓋平面，輸入保證橫向的骨牌（n個）之間不會相交，豎向的骨牌（m個）之間也不會相交，但橫豎之間可能相交，問拿去一些骨牌後，使得剩下的骨牌之間都不相交，最多剩下的多少骨牌(1 <= n, m <= 1000，骨牌的坐標為(x, y)(0 <= x, y <= 100))。

——>>第二場多校的一題，WA5個小時還是WA，難受啊。。。

策略：用並查集，相交點的兩張骨牌並在一個集合裡，但不能有環出現，那麼如果一個集合有k個元素，就可剩下(k + 1) / 2個。

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int maxn = 100 + 10;
const int maxv = 2000 + 10;
vector<int> G[maxn][maxn];
int f[maxv], w[maxv];

void init()
{
    int i, j;
    for(i = 0; i < maxn; i++)
        for(j = 0; j < maxn; j++)
            G[i][j].clear();
    for(i = 0; i < maxv; i++) f[i] = i;
    for(i = 0; i < maxv; i++) w[i] = 1;
}

int Find(int x)
{
    return x == f[x] ? x : Find(f[x]);
}

void Union(int x, int y)
{
    int newx = Find(x);
    int newy = Find(y);
    if(newx != newy)
    {
        f[newy] = newx;
        w[newx] += w[newy];
    }
}

int main()
{
    int n, m, x, y, i, j;
    while(scanf("%d%d", &n, &m) == 2)
    {
        if(!n && !m) return 0;
        init();
        for(i = 0; i < n; i++)
        {
            scanf("%d%d", &x, &y);
            G[y][x].push_back(i);
            G[y][x+1].push_back(i);
        }
        int N = n + m;
        for(i = n; i < N; i++)
        {
            scanf("%d%d", &x, &y);
            G[y][x].push_back(i);
            G[y+1][x].push_back(i);
        }
        for(i = 0; i <= 100; i++)
            for(j = 0; j <= 100; j++)
                if(G[i][j].size() == 2) {
                        Union(G[i][j][0], G[i][j][1]);}
        int ret = 0;
        for(i = 0; i < N; i++) if(f[i] == i) ret += (w[i] + 1) / 2;
        printf("%d\n", ret);
    }
    return 0;
}