AtCoder が提供しているABC（AtCoder Beginner Contest）352 のE問題をC++で解いてみました。ABC352は、2024年5月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Clique Connect（Difficulty : 1030）
問題はリンク先をご覧ください。
重みが少ない辺から統合していきますが、一工夫必要です。AtCoder Problems による Difficulty は 1030 でした。
解答案
最小全域木を求める問題です。なお、最小全域木については、「典型アルゴリズム問題集」のF問題で紹介しています。
重みが少ない辺から統合していきます。ただし、設定されている辺の数が多く、すべてを統合していっては時間が足らなくなります。
$K_i$ 頂点からなる頂点の部分集合 $S_i$ 内には、$K_i \times (K_i \; – \; 1) / 2$ 個の辺があります。これらの辺をすべて統合する必要はありません。$K_i – 1$個の辺を統合すれば、部分集合 $S_i$ 内は連結します。以下の制約があり、時間的にも間に合います。
$$\sum^{M}_{i=1} K_i \leqq 4 \times 10^5$$
C++ プログラム例（ABC352E）
$S_i$ 内の辺のコスト $C_i$ とインデックスをまとめてソートします。重みが小さい方から、辺を統合します。統合には、ACL の UnionFind を使いました。それぞれの $S_i$ の辺は、$K_i – 1$ 本だけ統合しています（32行目のfor文）。
頂点1に統合されている頂点数を調べて、それが $N$ に一致していなければ、全体が連結していません（40行目のif文）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
typedef long long int ll;
int main()
{
int n, m;
cin >> n >> m;
vector<int> k(m);
vector<ll> c(m);
vector<vector<int>> a(m);
vector<pair<int, int>> order_c;
for (int i = 0; i < m; ++i) {
cin >> k[i] >> c[i];
for (int j = 0; j < k[i]; ++j) {
int t;
cin >> t;
a[i].push_back(t);
}
order_c.push_back(make_pair(c[i], i));
}
sort(order_c.begin(), order_c.end());
ll result = 0;
dsu uf(n + 1);
for (int i = 0; i < m; ++i) {
ll cost = order_c[i].first;
int index = order_c[i].second;
for (int j = 0; j < k[index] - 1; ++j) {
if (!uf.same(a[index][j], a[index][j + 1])) {
uf.merge(a[index][j], a[index][j + 1]);
result += cost;
}
}
}
if (uf.size(1) != n) {
result = -1;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python は、標準ライブラリに UnionFind がないため、プログラムの紹介を省略します。
最後に
E問題が解けることは珍しいのですが、最小全域木については相性が良かったのか解くことができました。
引き続き ABC の問題を紹介していきます。
