大家好，我是小码匠，今天分享上周末AtCoder线上赛-ABC329的F题。
前置知识
- set
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成：10道
- 待完成：290道
题目描述
官方原题：
- https://atcoder.jp/contests/abc329/tasks/abc329_f
- 洛谷：https://www.luogu.com.cn/problem/AT_abc329_f
输入数据1
代码语言：javascript复制6 5
1 1 1 2 2 3
1 2
6 4
5 1
3 6
4 6
输出数据1
代码语言：javascript复制1
2
1
1
3
输入数据 2
代码语言：javascript复制5 3
2 4 2 4 2
3 1
2 5
3 2
输出数据 2
代码语言：javascript复制1
2
0
题解
- 看见题目询问种类数，优先想到set，set其中一个特性就是不包含重复值，很方便我们统计
- set里面有一个函数，叫insert，可以合并两个集合，但请注意，它原来的集合里面的数是不变的
- 通俗点讲，
set_x 里面的数现在要合并到
set_y 里面，合并操作完成后，
set_y 里面包含了
set_x 的数，但
set_x 里面的数仍然存在，所以还要清除
- 这个时候，我们发现，假如我们直接按题目要求把
合并到
里面，当
里面的数太多时，容易超时，所以我们一定是将数少的一方合并到数多的一方
- 合并完成后我们发现，这种合并方式会导致set里的数是混乱的，比如本来是
里的数合并到
里面，但现在数都在
里，所以我们还要在实行一步交换
- 交换操作可以用swap函数很方便的完成，swap函数复杂度很低，不用担心超时
赛场代码
- 6个测试点TLE
#include <bits/stdc .h>
using namespace std;
//bitset<200001> g[200001];
void best_coder() {
int n, q;
cin >> n >> q;
vector<set<int>> g(n);
vector<int> l(n, 1);
for (int i = 0; i < n; i) {
int a;
cin >> a;
g[i].insert(a);
}
for (int i = 0; i < q; i) {
int x, y;
cin >> x >> y;
--x;
--y;
if (l[x]) {
g[y].insert(g[x].begin(), g[x].end());
g[x].erase(g[x].begin(), g[x].end());
l[x] = 0;
l[y] = g[y].size();
}
cout << l[y] << endl;
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
void best_coder() {
int n, q;
cin >> n >> q;
vector<set<int>> g(n);
vector<int> l(n, 1);
for (int i = 0; i < n; i) {
int a;
cin >> a;
g[i].insert(a);
}
for (int i = 0; i < q; i) {
int x, y;
cin >> x >> y;
--x;
--y;
if (l[x] < l[y]) {
g[y].insert(g[x].begin(), g[x].end());
g[x].clear();
l[x] = 0;
l[y] = g[y].size();
} else {
g[x].insert(g[y].begin(), g[y].end());
g[y].clear();
l[x] = 0;
l[y] = g[x].size();
swap(g[x], g[y]);
}
cout << l[y] << 'n';
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
END
