Codeforces 1013D Chemical table

题面在这里

题意：\(n\times m\)的矩阵，初始有一些点，任意矩形的三个角有点，第四个角就自动生成点，可以在中途加点，问最终把矩阵填满需要至少加几个点

​

很巧妙的转化……

考虑每个点连接了它所在的行和列

用并查集维护

那么有矩形的三个顶点，就会把两行两列合并到同一个联通块，相当于有第四个顶点

在同一个集合的行和列，他们的交点就有数字

那么最后答案就是联通块个数-1

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=400005;
int n,m,q,fa[maxn];
int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for (int i=1;i<=n+m;i++) fa[i]=i;
	for (int i=1;i<=q;i++){
		int x,y;scanf("%d%d",&x,&y);y+=n;
		fa[getfa(x)]=getfa(y);
	}
	int ans=-1;
	for (int i=1;i<=n+m;i++) if (fa[i]==i) ans++;
	printf("%d",ans);
	return 0;
}