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

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

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

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
}

------ 本文结束 ------