题意：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;
}