この問題の背景

競技プログラミングでは、グラフに関する問題が非常に多く出題されます。グラフの情報を管理するための代表的な手法に隣接行列と隣接リストがあります。

単純無向グラフにおける隣接行列とは、各成分が \(0\) または \(1\) である \(N \times N\) の行列であり、頂点 \(u, v\) を結ぶ辺が存在するならば \(A_{u, v}\) と \(A_{v, u}\) は \(1\) であり、存在しないならば \(0\) です。また、隣接リストとは、各頂点 \(u\) について、\(u\) と辺で結ばれている頂点のリスト \(a_u = (a_{u, 1}, \dots, a_{u, d_u})\) を管理するというものです。なお、\(u\) と辺で結ばれた頂点の個数、すなわち \(d_u\) を頂点 \(u\) の次数と呼びます。

ここまでお読みの方はお気づきかもしれませんが、この問題で出力することが要求されているのは、隣接リストそのものです。グラフに関する問題を解くための第一歩として、実装の基本を身につけるというのがこの問題の目的です。

解法

ここでは、グラフ理論の用語を用いて、都市を「頂点」と、道路を「辺」と呼ぶことにします。

C++ / Python それぞれについて説明します。

C++

C++ でリストを表現するためには std::vector というデータ構造を用います。ある型 T に対し、std::vector<T> を用いると型が T であるようなデータの列を格納することができます。この問題では、各頂点に対し、その頂点と辺で結ばれた頂点の番号の列を管理するので、std::vector<int> の列、すなわち std::vector<std::vector<int>> を用いればよいことがわかります。

空の std::vector<int> が \(n\) 個並んでいるようなstd::vector<std::vector<int>> を用意するためには、次のようにします。

vector<vector<int>> a(n);

\(0 \leq i \lt n\) に対し、a[i] は \(i\) 番目の std::vector<int> を表します。要素を追加するためには、メンバ関数である std::vector::push_back を用います。\(i\) 番目のリストに整数 \(x\) を追加するためには、

a[i].push_back(x);

のようにします。

また、std::sort 関数を用いると、要素を昇順に並べ替えることができます。

実装例は次のようになります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        a[u - 1].push_back(v);
        a[v - 1].push_back(u);
    }
    for (int i = 0; i < n; ++i) {
        sort(begin(a[i]), end(a[i]));
        cout << size(a[i]);
        for (int a : a[i]) {
            cout << ' ' << a;
        }
        cout << '\n';
    }
    return 0;
}

Python

Python でリストを表現するためには list というデータ構造を用います。C++ とは異なり、Python のリストには型が異なる要素を格納することができます。例えば、同じリストに整数型のデータと文字列型のデータを格納することができます。

n 個の空のリストが並んだリストを宣言するには、次のようにします。

a = [[] for _ in range(n)]

Python の list への要素の追加は、append メソッドを用います。\(i\) 番目のリストに整数 \(x\) を追加するためには、

a[i].append(x)

のようにします。

また、sort メソッドを用いて要素を昇順に並べ替えることができます。

実装例は次のようになります。

n, m = map(int, input().split())
a = [[] for _ in range(n)]

for _ in range(m):
  u, v = map(int, input().split())
  a[u - 1].append(v);
  a[v - 1].append(u);

for (i, v) in enumerate(a):
  v.sort()
  print(len(v), *v)