题目链接:http://codeforces.com/contest/1013/problem/D
题目大意:
给出一个 \(n \times m\) 的表格,表格上有一些初始点。若有这样的三个点:\((r_1, c_1), (r_1, c_2), (r_2, c_1)\),则由这三个点能生成出点 \((r_2, c_2)\)。现问在初始点的基础上最少添加多少个点,能使得初始点和添加的点及它们生成出来的点能填满整个表格。
知识点: 并查集
解题思路:
可以将每一个点看成是将所在的行和列联系起来。如此一来,对于 \((r_1, c_1) + (r_1, c_2) + (r_2, c_1) \Rightarrow (r_2, c_2)\),我们可以理解为:因为 \(r_1\) 和 \(c_1\),\(r_1\) 和 \(c_2\),\(r_2\) 和 \(c_1\) 都相应地联系起来了,那么 \(r_2\) 和 \(c_2\) 也联系起来了。所以我们只要把所有的行和列都联系起来,生成出来的点就能填满整个表格。那么问题就转换成问最少建立多少联结,能将所有的行和列都联系起来。可以用并查集解决。
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MAXN=+;
const int INF=0x3f3f3f3f;
const int MOD=1e9+; int fa[MAXN<<];
int finds(int x){
if(fa[x]==x) return x;
return fa[x]=finds(fa[x]);
}
int main(){
int r,c,n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n+m;i++) fa[i]=i;
for(int i=;i<q;i++){
scanf("%d%d",&r,&c);
int f1=finds(r),f2=finds(c+n);
if(f1!=f2) fa[f1]=f2;
}
int ans=;
int root=finds();
for(int i=;i<=n+m;i++){
int temp=finds(i);
if(temp!=root){
ans++;
fa[temp]=root;
}
}
printf("%d\n",ans);
return ;
}