CF-1012

B. Chemical table

题意

一个 n*m 的矩阵，当涂了三个角时，会自动涂第四个，已有一些点涂色，问最少需要涂几个点。

题解

只需n+m-1个就可以填满,
当插入点(x1,y1) 时有关系x1<=>y1
当插入点(x2,y1) 时有关系 x2<=>y1<=>x1
当插入点(x1,y2) 时有关系 y2<=>x1<=>y1<=>x2
用并查集来连接

代码

#include <bits/stdc++.h>
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define inlld(lld) scanf("%lld",&lld)
typedef unsigned long long ull;
#define inlf(f) scanf("%lf",&f)
#define ind(d) scanf("%d",&d)
#define ins(s) scanf("%s",s)
#define inf 0x3f3f3f3f
typedef long long ll;
#define pi acos(-1.0)
#define mod (int)(1e9+7)
#define N (int)(4.1e5)
using namespace std;

int uni[N+1];
void init(){
  for1(i,N)uni[i]=i;
}
int find_root(int x){
  if (uni[x]==x) return x;
  else return uni[x]=find_root(uni[x]);
}
int main() {
#ifndef ONLINE_JUDGE
  // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
  // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat","w",stdout);
#endif
  //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  init();
  int n,m,q,r,c,ans=0;
  scanf("%d%d%d",&n,&m,&q);
  for0(i,q){
    scanf("%d%d",&r,&c);
    uni[find_root(m+r)]=find_root(c);
  }
  for1(i,n+m)if(uni[i]==i)ans++;
  printf("%d\n",ans-1);
  return 0;
}