原题链接
题意:（from洛谷）
给你一个n*m的矩形，一开始有q个格子上被标记。对于任意两行两列，如果交汇的四个格子中有三个被标记，那么第4个会被自动标记。问你至少需要手动标记几个格子，使得整个矩形内的格子都被标记。
思路：
假设交汇的四个格子的坐标是(x1,y1),(x1,y2),(x2,y1),(x2,y2).
那么这四个点里有任意三个点被标记后，第四个也能够被标记，也就是说第四个点是(x1,y1),那么它能够被标记的条件就是x1和y1在一个连通块里.
也就是说，在一个连通块里的坐标构成的任意点都能够被标记，所以手动标记就只需要将这几个连通块连接起来，也就是连通块的数量-1.
连通块的话就用并查集维护，因为最多有n行，所以可以将列的标号记作i+n，这样行列之间不会产生冲突。
代码：
#pragma GCC optimize(3) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } const ll inf = 0x3f3f3f3f3f3f3f3f; const int maxn=1e6+7,mod=1e8; const double PI = atan(1.0)*4; const double eps=1e-6; int root[maxn],n,m,q; int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } int main(){ n=read(),m=read(),q=read(); for(int i=1;i<=n+m;i++) root[i]=i; for(int i=1;i<=q;i++){ int r=read(),c=read(); c+=n; r=Find(r),c=Find(c); if(r!=c) root[r]=c; } int res=0; for(int i=1;i<=n+m;i++) if(Find(i)==i) res++; out(res-1); return 0; }
