Codeforces 1013D Chemical table

题面在这里

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

很巧妙的转化……

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

用并查集维护

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

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

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

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}