Description：

给一个网格图，如果一个矩形四个角中的三个已经有了，那就可以获得剩下的那个角，可以购买一些位置，问最少要买几个。

$1\le n ,m,q\le 200000$

Solution：

根据网格图的常用套路，把行和列看成点格子看成边，那么整张图就变成了一个二分图，发现获得最后一个角的操作不会改变图的连通性，而最后结果所有部分一定是连起来的，所以只要把各个联通块连起来即可，于是最终的答案就是联通块个数 $-1$ ，用并查集就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 200010

int f[MAXN << 1];

int find(int x){return (f[x] == -1 ? x : f[x] = find(f[x]));}

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	int cnt = n + m;

	memset(f,-1,sizeof(f));

	int a,b;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&a,&b);b = b + n;

		int p = find(a),q = find(b);

		if(p == q)continue;

		f[p] = q;--cnt;

	}

	cout << cnt - 1 << endl;

	return 0;

}