Codeforces 731C Socks

链接

传送门

题意

有$n$只袜子,$m$天,每天给出两只要穿的袜子,要求每天穿的袜子的颜色相同,问最少改变几只袜子的颜色。

思路

同一天要穿的袜子之间连一条边,然后求并查集中最多的颜色,每个并查集颜色的总数与最多颜色的差的和即为答案。

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 200010;
int c[maxn], p[maxn];
vector<int> g[maxn];
int Find(int x) {
return x == p[x] ? x : p[x] = Find(p[x]);
}
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
p[i] = i;
scanf("%d", &c[i]);
}
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
int fu = Find(u), fv = Find(v);
p[fu] = fv;
}
for (int i = 1; i <= n; ++i) {
g[Find(i)].push_back(c[i]);
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
int Max = 0, tmp = 0, pre = -1;
sort(g[i].begin(), g[i].end());
for (int x: g[i]) {
if (x != pre) {
tmp = 0;
}
Max = max(Max, ++tmp);
pre = x;
}
ans += int(g[i].size()) - Max;
}
printf("%d\n", ans);
return 0;
}

支付宝扫码领红包