Background of this problem

In competitive programming, we regularly see problems related to graphs. There are two main ways to manage the information of a graph: an adjacency matrix and an adjacency list.

The adjacency matrix of a simple undirected graph is a \(N \times N\)-matrix whose elements are \(0\) or \(1\), in which \(A_{u, v}\) is \(1\) if there is an edge connecting vertices \(u\) and \(v\), and \(0\) otherwise. On the other hand, the adjacency list is used to manage the list \(a_u = (a_{u, 1}, \dots, a_{u, d_u})\) of vertices connected with \(u\) by edges (or “adjacent to \(u\)”), for each vertex \(u\). Here, the number of vertices adjacent to \(u\), \(d_u\), is called the degree of vertex \(u\).

Some of the readers may have realized that this problem asks to print nothing but the adjacency list. The purpose of this problem is to learn the basics of implementation in order to solve the problem related to graphs.

Solution

In this article, we call a city “a vertex” and a road “a edge” using the terms of graph theory.

We describe the solutions using C++ and Python.

C++

In C++, a list is represented by a data structure named std::vector. For a type T, we can use std::vector<T> to store a sequence of data of type T. In this problem, we need to manage the sequence of vertices adjacent to each vertex, so it is sufficient to use a sequence of std::vector<int>, that is, a std::vector<std::vector<int>>.

We can write as follows to prepare a std::vector<std::vector<int>> consisting of \(n\) empty std::vector<int>s:

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

For each \(0 \leq i \lt n\), a[i] represents the \(i\)-th std::vector<int>. In order to append an element, we use the member function std::vector::push_back. We can push an integer \(x\) to the \(i\)-th list by:

a[i].push_back(x);

Finally, you can use the function std::sort to sort the elements in ascending order.

The following is a sample code.

#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

In Python, we use a data structure list to represent a list. Unlike C++, Python’s list can store data of different types. For example, the same list can contain integer-typed data and string-typed data simultaneously.

We use the following statement to declare a list of n empty lists:

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

Pushing an element to Python list can be accomplished by the method append. In order to push an integer \(x\) to the \(i\)-th list, we write as follows:

a[i].append(x)

The sort method allows us to sort the elements in ascending order.

The following is a sample code:

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)