AtCoder が提供しているABC（AtCoder Beginner Contest）302 のF問題をC++とPythonで解いてみました。ABC302は、2023年5月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Merge Set（Difficulty : 1430）
問題はリンク先をご覧ください。
超頂点というテクニックを使って解くことができました。AtCoder Problems による Difficulty は 1430 でした。
解答案
「超頂点」という考え方を導入します。$S_i$ の添え字も頂点の番号も0からカウントします。
- 頂点 0 から $N-1$ を $S_i$ と同一視します。
- 頂点 $N$ から $N + M – 1$ と頂点 0 から $M-1$ と同一視します。
- $S_i$ から $S_i$ が含む頂点に辺を設定します。
- 頂点 $N$ から頂点 $N + M – 1$ への（最小）距離が分かると、問題の操作の最小回数が分かります。ただし、同じ $S_i$ に入っている場合の距離が2となり、ひとつの集合 $S_i$ から $S_j$ に移動するための距離も2であるため、(距離-2)/2 が求める操作の最小回数となります。
C++ プログラム例（ABC302F）
上記の方針で、辺を設定します（13ー23行目）。BFS（キュー）を使って頂点 n から連結している頂点への距離を求めます。頂点 n + m – 1 までの距離を使って最小回数を求めます。連結していない場合は、-1 を出力します（39ー43行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<int> dist;
int main()
{
int n, m;
cin >> n >> m;
G.resize(n + m);
dist.assign(n + m, -1);
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
for (int j = 0; j < a; ++j) {
int s;
cin >> s;
--s;
G[i].push_back(n + s);
G[n + s].push_back(i);
}
}
queue<int> que;
que.push(n);
dist[n] = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v] == -1) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}
if (dist[n + m - 1] != -1) {
cout << (dist[n + m - 1] - 2) / 2 << endl;
} else {
cout << "-1" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC302F）
C＋＋ と同じ考え方で実装しました。キューとして collections モジュールの deque を使いました。以下が Python プログラムです。
"""AtCoder Beginner Contest 302 F"""
from collections import deque
n, m = map(int, input().split())
G = [[] for _ in range(n + m)]
dist = [-1] * (n + m)
for i in range(n):
a = int(input())
s = list(map(int, input().split()))
for j in range(a):
G[i].append(n + s[j] - 1)
G[n + s[j] - 1].append(i)
que = deque()
que.append(n)
dist[n] = 0
while que:
now = que.popleft()
for next_v in G[now]:
if dist[next_v] == -1:
que.append(next_v)
dist[next_v] = dist[now] + 1
print((dist[n + m - 1] - 2) // 2 if dist[n + m - 1] != -1 else -1)最後に
コンテスト中には、この問題を解くことができませんでした。コンテスト後に公式解説を読み超頂点というテクニックを理解することができました。うまい考え方だと感心しました。
もし、このテクニックをコンテスト中に気が付いて解くことができたら、非常に気分が良いと思います。
引き続き ABC の問題を紹介していきます。
