AtCoder が提供しているABC（AtCoder Beginner Contest）372 E問題をC++で解いてみました。ABC372は、2024年9月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 K-th Largest Connected Components（Difficulty : 1042）
問題の詳細は、リンク先をご覧ください。
ABC372 E問題 K-th Largest Connected Components
UnionFindで統合したときに番号の大きな頂点を再計算します。AtCoder Problems による Difficulty は 1042 でした。
解答案
UnionFind で統合したときに、頂点が大きな順に番号を配列に格納します。$1 \leqq k \leqq 10$ であるため、最大10個格納すればクエリの処理ができます。
C++ プログラム例（ABC372E）
プログラムの補足です。
- ACL（AtCoder Library）の UnionFind を使います（2、4行目）。
- それぞれの頂点と連結している頂点番号の順に配列
pointsに最大10個記憶します。- 初期値は、その頂点自身しかありません（24ー27行目）。
- タイプ1のクエリでは、関数
merge_vでpointsを更新します（6ー18行目）。
- タイプ2のクエリでは、指定された頂点と連結している $k$ 番目の頂点番号の要素を出力します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
void merge_v(vector<int>& u_vector, vector<int>& v_vector)
{
vector<int> t = u_vector;
for (int i = 0; i < (int)v_vector.size(); ++i) {
t.push_back(v_vector[i]);
}
sort(t.begin(), t.end(), greater<int>());
u_vector.clear();
for (int i = 0; i < min(10, (int)t.size()); ++i) {
u_vector.push_back(t[i]);
}
}
int main()
{
int n, q;
cin >> n >> q;
vector<vector<int>> points(n + 1);
for (int i = 1; i <= n; ++i) {
points[i].push_back(i);
}
dsu uf(n + 1);
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
int u, v;
cin >> u >> v;
if (!uf.same(u, v)) {
int pre_u = uf.leader(u);
int pre_v = uf.leader(v);
uf.merge(u, v);
if (uf.leader(u) == pre_u) {
merge_v(points[pre_u], points[pre_v]);
} else {
merge_v(points[pre_v], points[pre_u]);
}
}
} else if (type == 2) {
int v, k;
cin >> v >> k;
if ((int)points[uf.leader(v)].size() < k) {
cout << -1 << endl;
} else {
cout << points[uf.leader(v)][k - 1] << endl;
}
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python は、標準ライブラリで UnionFind がありません。プログラムの紹介を省略します。
最後に
$k$ の制約が小さいことがポイントでした。UnionFind について理解を深めることができました。
引き続き ABC の問題を紹介していきます。
