Codeforces 1013D(并查集维护行列)

Codeforces 1013D
题意：一个矩形的其中三个顶点有东西的话第四个顶点也会有东西, 然后问你铺满网格最少需要买多少东西。

维护行列方法：并查集、图论、2-SAT、二分图
这里用并查集。我们根据三个点坐标，发现如果连上$(r1, c1), (r1, c2), (r2, c1)$无向边，则$(r2, c2)$连通，相当于这个点存在了。所以我们用并查集连边，判断连通块个数$siz$，买$siz-1$个点使得整个图连通即可。

Codeforces Submission

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, m, q, f[400000 + 5];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void clean() {}
int solve() {
    clean();
    for (int i = 1; i <= n + m; i++) f[i] = i;
    while (q--) {
        int r, c; cin >> r >> c;
        int x = find(r), y = find(c + n);
        if (x != y) f[x] = y;
    }
    int ans = 0;
    for (int i = 1; i <= n + m; i++) if (f[i] == i) ans++;
    cout << ans - 1;
    return 0;
}
int main() {
    cin >> n >> m >> q, solve();
    return 0;
}