AtCoder が提供しているABC（AtCoder Beginner Contest）276 のB問題をC++とPythonで解いてみました。ABC276は、2022年11月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Adjacency List（Difficulty : 143）
問題はリンク先をご覧ください。
グラフを読み込む問題です。AtCoder Problems による Difficulty は、143 でした。
解答案
問題を解く方針を書きだします。
- n と m を読み込む。
- m 個の辺（edge）を読み込み、頂点に登録する。
- 各頂点に登録した頂点をソートする。
- 頂点毎に隣接している頂点を表示する。
C++ プログラム例（ABC276B）
グラフを表現することは、ABC270 C問題でも紹介しました。そこで紹介したコードパターンを再掲します。
グラフの表現は、隣接リスト表現と呼ばれる、頂点 u から隣接している集合 vector e[u] を定義する方法がよく使われます。N 個の頂点と N – 1 個の辺を持つグラフの入力をするコードは以下となります。なおこの問題では向きを持たないため、両方向の登録をしています（10行目と11行目）。
vector<int> e[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
return 0;
}CとC++の配列は、0からアクセスします（0オリジン）。このため、頂点に辺を登録する場合、頂点番号を1引いて登録します。解として表示するときは、1足して表示します。
このプログラムでは、一貫して、頂点番号を0からカウントしています。関連するコードの背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> e[n];
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
e[u - 1].push_back(v - 1);
e[v - 1].push_back(u - 1);
}
for (int i = 0; i < n; ++i) {
cout << e[i].size();
if (e[i].size() > 0) {
sort(e[i].begin(), e[i].end());
for (int j = 0; j < e[i].size(); ++j) {
cout << " " << e[i][j] + 1;
}
}
cout << endl;
}
return 0;
}ただし、0オリジンは1個違いのミスをする可能性があります。このため、問題で与えられている1オリジンのまま処理するプログラムを紹介します。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> e[n + 1];
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
cout << e[i].size();
if (e[i].size() > 0) {
sort(e[i].begin(), e[i].end());
for (int j = 0; j < e[i].size(); ++j) {
cout << " " << e[i][j];
}
}
cout << endl;
}
return 0;
}差分の背景色を変更しました。1オリジンの場合、引いたり足したりすることがないため、ミスは少ないと思います。
ただし、各頂点と接続している頂点を表現する vector<int> の配列を n + 1 個確保する必要があります。これは、e[n] までアクセスするためです。また、e[0] は確保していますが、使いません。
グラフの処理は、問題の書き方に合わせるとミスが少なくなると思います。
Python プログラム例（ABC276B）
Python は、可読性を高くすることを意識して、1オリジンで記載しました。
"""AtCoder Beginner Contest 276 B"""
n, m = map(int, input().split())
e = [[] for i in range(n + 1)]
for i in range(m):
u, v = map(int, input().split())
e[u].append(v)
e[v].append(u)
for i in range(1, n + 1):
print(len(e[i]), end="")
if len(e[i]) > 0:
e[i].sort()
print("", *e[i])
else:
print("")こちらも「AC」と判定されました。
最後に
グラフの辺を読み込み、接続している頂点を出力する基本的な問題です。
C++ では、0オリジンの場合と1オリジンの場合を紹介しました。アルゴリズムの教科書は無駄な領域がないため、0オリジンで書いてあることが多いです。一方、AtCoder の問題は、表現が自然に感じる1オリジンで書いてあることが多いです。
求められている場合に合わせることが重要だと考えています。
引き続き ABC の問題を紹介していきます。
