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; }