留下的数目 = 连通的木块的数目 - 连通的木块的数目/2.....

并查集维护即可......

Warm up 2

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

4
6

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int tu[110][110],n,m;

int fa[2100],sz[2100];
int vis[4100];

int Find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=Find(fa[x]);
}

void Union(int a,int b)
{
    a=Find(a),b=Find(b);
    if(a==b) return ;
    if(sz[a]<sz[b])
    {
        fa[b]=a;
        sz[a]+=sz[b];
    }
    else
    {
        fa[a]=b;
        sz[b]+=sz[a];
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        for(int i=0;i<2100;i++)
            fa[i]=i,sz[i]=1;
        memset(tu,0,sizeof(tu));
        int cnn=0,cnm=n,x,y;
        for(int i=0;i<n;i++)
        {
            cnn++;
            scanf("%d%d",&x,&y);
            tu[x][y]=tu[x+1][y]=cnn;
        }
        for(int i=0;i<m;i++)
        {
            cnm++;
            scanf("%d%d",&x,&y);
            ///x,y+1
            if(tu[x][y])
            {
                Union(tu[x][y],cnm);
            }
            if(tu[x][y+1])
            {
                Union(tu[x][y+1],cnm);
            }
        }
        int ans=0;
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=n+m;i++)
        {
            int f=Find(i);
            if(vis[f]) continue;
            vis[f]=true;
            ans+=sz[f]-sz[f]/2;
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDOJ 4619 Warm up 2,布布扣,bubuko.com

HDOJ 4619 Warm up 2

原文：http://blog.csdn.net/ck_boss/article/details/24559039