Codeforces 731C Socks

发表于 分类于 Disqus：

链接

传送门

题意

有\(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;
}
相关文章