给定的一个n*m的区域内，给出一些点的坐标，这些点上有一个元素，如果在矩形的子矩形的三个点都有元素，那么第四个点的元素可以自己产生，其他的元素需要购买，问最少需要购买多少中元素才可以把这个区域给填满。
对于给出点的，先用并查集把x轴上和y轴上有联系的点都联系起来，并且可以顺便把出现过的x和y的数值标记起来。
如果我把所有的点分成了n块，那么的需要添加n-1个元素来把这n块连接起来。对于没有出现的x和y的数值，我需要额外买一个元素来填充这个点。
因为我已经在一个块内的点一定是有联系的，而另一个块的点一定与这里面的点都没有联系，所以我只需要添加一个元素让他们的 x 或者 y 联系起来，那么这个块一定可以形成一个包含三个点的子矩形，也就可以产生出另一个点的元素。就可以把这些块里出现的x和y的横纵方向填满，这样就会剩下那么没有出现的x和y位置上的点还是空的了，然后同样的也只需要添加一个就可以填满一行或者一列。
#include<map> #include<set> #include<ctime> #include<cmath> #include<stack> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define lowbit(x) (x & (-x)) typedef unsigned long long int ull; typedef long long int ll; const double pi = 4.0*atan(1.0); const int inf = 0x3f3f3f3f; const int maxn = 200005; const int maxm = 1000005; const int mod = 10007; using namespace std; int n, m, tol, T; int fa[maxn]; int X[maxn]; int Y[maxn]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void build(int x, int y) { int u = find(x); int v = find(y); fa[v] = u; } int main() { int q; scanf("%d%d%d", &n, &m, &q); for(int i=1; i<=q; i++) fa[i] = i; int x, y; for(int i=1; i<=q; i++) { scanf("%d%d", &x, &y); if(X[x]) build(i, X[x]); X[x] = fa[i]; if(Y[y]) build(i, Y[y]); Y[y] = fa[i]; } ll ans = -1; for(int i=1; i<=q; i++) find(i); for(int i=1; i<=q; i++) if(fa[i] == i) ans++; for(int i=1; i<=n; i++) if(!X[i]) ans++; for(int i=1; i<=m; i++) if(!Y[i]) ans++; printf("%I64d ", ans); return 0; }