Magical bipartite graph connected block problem.

General idea of the topic

Given a matrix with \ (n \) rows \ (m \) columns, there are \ (q \) elements \ ((x_i,y_i) \) as \ (1 \), and the rest are \ (0 \). If the elements on \ ((x,y), (x,y'), (x',y) \) are all \ (1 \), you can also extend the elements on \ ((x',y') \) to \ (1 \).

At least a few \ (0 \) need to be changed into \ (1 \) in the initial matrix, so that the whole matrix can change all elements into \ (1 \) through the extension of the above rules\ (m,n,q\le 2\times 10^5\).

General idea

This kind of matrix problem has a routine bipartite graph modeling method: take the \ (n \) line as \ (n \) left points, number \ (1\sim n \)\ (m \) column as \ (m \) right point, number \ (n+1\sim n+m \). We make all elements with a value of \ (1 \) on \ ((x,y) \) directly connected to each other in \ ((x,y+n) \). The final state required by the topic is that the elements of each position are \ (1 \), that is, the bipartite graph constitutes a complete bipartite graph.

Consider the extension rules in the topic\ The elements on ((x,y), (x,y'), (x',y) \) are all \ (1 \), which is equivalent to that there are connecting edges between \ ((x,y), (x,y'), (x',y) \), then \ (x,y,x',y' \) constitutes a connected block. Obviously, after adding the edge \ ((x',y') \), the number of connected blocks will not change. Assuming that the original bipartite graph has \ (C \) connected blocks, no matter how each connected block connects its edges, it will not reduce \ (C \). In order to make \ (C \) become \ (1 \), at least \ (C-1 \) edges need to be connected (because the connected block may need additional edges to become a complete bipartite graph). So \ (ans\ge C-1 \).

Next, it is proved that \ (ans =C-1 \) is feasible. Consider two points \ (u,v \) in a connection block. The ultimate goal is to ensure the connection between \ (u,v \).

• If \ ((u,v)\in E \), then it is established directly.
• If \ ((U, V) \ not e \), there must be another left point \ (x \) and right point \ (Y \), so that \ ((u,y),(x,v)\in E \) and there is a path of \ (y\to x \), as shown in the following figure.

Since both zigzag and Youzi lines meet the expansion conditions, the zigzag can be connected repeatedly on the \ (y\to x \) path, and finally a large Youzi will be formed, and then \ (u,v \) can be connected. This proves that any two points in the same connected block can be automatically connected by extension, so only \ (C-1 \) edges need to be connected.

Complete code

#include <bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, int> PII;
const int maxn = 4e5 + 5;
namespace IO_ReadWrite {
	#define re register
	#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
	char _buf[1<<21], *p1 = _buf, *p2 = _buf;
	template <typename T>
	inline void read(T &x){
		x = 0; re T f=1; re char c = gg;
		while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
		while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
		x *= f;return;
	}
	inline void ReadChar(char &c){
		c = gg;
		while(!isalpha(c)) c = gg;
	}
	template <typename T>
	inline void write(T x){
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x/10);
		putchar('0' + x % 10);
	}
	template <typename T>
	inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
int hd[maxn], ver[maxn], nxt[maxn], tot, n, m, q, ans;
inline void add(int u, int v) {
	ver[++tot] = v; nxt[tot] = hd[u]; hd[u] = tot;
	ver[++tot] = u; nxt[tot] = hd[v]; hd[v] = tot;
}
bool vis[maxn];
inline void dfs(int u) {
	for(int i = hd[u]; i; i = nxt[i]) {
		int v = ver[i];
		if(vis[v]) continue;
		vis[v] = 1;
		dfs(v);
	}
}
int main () {
	read(n); read(m); read(q);
	rep(i, 1, q) {
		int x, y;
		read(x); read(y);
		add(x, y + n);
	}
	rep(u, 1, n + m) if(!vis[u]) {
		vis[u] = 1;
		ans ++;
		dfs(u);
	}
	writeln(ans - 1);
	return 0;
}