731-C. Socks
Tags: disjoint-set
出處：https://codeforces.com/contest/731/problem/C
提交：https://codeforces.com/contest/731/submission/107328843
問題：給定 $n\in[2,200000]$ 隻襪子 (1 ~ n)、$k\in[1,200000]$ 種顏色 (1 ~ k)，每隻襪子都有各自的顏色，接著有 $m\in[0,200000]$ 筆資料說明 a 和 b 兩隻襪子應該要同色。請問至少需要改變幾隻襪子的顏色才能符合需求。
解法：這題也是典型的並查集，只是需要一個額外的陣列去記錄每個集合 (應該要彼此同色的襪子們) 裡面各種顏色襪子的數量，然後計算所有「非眾色」的襪子總數而已。
實作：
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
|
#include <bits/stdc++.h>
using namespace std;
int p[200001]; // parent
int c[200001]; // color
map<int, int> cctr[200001]; // color counter
int find(int x) {
return x == p[x] ? x : (p[x] = find(p[x]));
}
int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
int n, m, k, a, b;
cin >> n >> m >> k;
for (int i=1; i<=n; i++) {
cin >> c[i];
p[i] = i;
}
for (int i=0; i<m; i++) {
cin >> a >> b; a = find(a); b = find(b);
if (cctr[a].empty()) cctr[a].insert(pair<int, int>(c[a], 1));
if (cctr[b].empty()) cctr[b].insert(pair<int, int>(c[b], 1));
if (a != b) {
if (cctr[a].size() < cctr[b].size()) swap(a, b);
for (auto it = cctr[b].begin(); it != cctr[b].end(); it++) {
auto it2 = cctr[a].find(it->first);
if (it2 == cctr[a].end()) cctr[a].insert(pair<int, int>(it->first, it->second));
else it2->second += it->second;
}
cctr[b].clear();
p[b] = a;
}
}
int final_sum = 0;
for (int i=1; i<=n; i++) {
int max = 0;
for (auto it = cctr[i].begin(); it != cctr[i].end(); it++) {
final_sum += it->second;
if (max < it->second)
max = it->second;
}
final_sum -= max;
}
cout << final_sum << endl;
return 0;
}
|
結果：
alan23273850 的刷題筆記