题目概述

如果存在 $(r_1,c_1),(r_2,c_2),(r_2,c_1),r_1\not=r_2,c_1\not=c_2$ 那么就可以不消耗费用添加 $(r_2,c_2)$ 。现在 $n\times m$ 的网格中已经有了 $q$ 个元素，问至少需要添加多少个元素使得网格被填满。

解题报告

CF好喜欢并查集转化啊……如果 $(x,y)$ 有元素，那么一旦有了 $(x,z)$ 的话 $y$ 和 $z$ 两列就同步了（同步之后每次添加都会让两列都加上一个元素），同理如果有了 $(x,y)$ 和 $(z,y)$ 的话 $x$ 和 $z$ 两行就同步了。

添加元素 $(x,y)$ 有什么意义呢？会发现这样让 $x$ 行和 $y$ 列连接起来，而如果 $x$ 行和 $y$ 列本身就和其他行和列相连的话这些行和列就会同步了。如果所有行和列都同步了那么就说明可以填满网格。

所以答案就是连通块个数 $-1$ ，因为添加一个元素就能合并两个连通块。

示例程序

这代码长度让我百感交集。

#include<cstdio>
using namespace std;
const int maxn=400000;

int n,m,te,fa[maxn+5],ans;

int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&te);for (int i=1;i<=n+m;i++) fa[i]=i;
    for (int x,y;te;te--) scanf("%d%d",&x,&y),x=getfa(x),y=getfa(y+n),fa[x]=y;
    for (int i=1;i<=n+m;i++) if (i==getfa(i)) ans++;return printf("%d\n",ans-1),0;
}