Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 276 B問題 Adjacency List

AtCoder ABC276 ABC B問題 200 pts

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E)$ が与えられる. なお,

$V=\{1,2, \dots, N\}$
$E=\{A_j B_j \mid j=1,2, \dots, M\}$

である.

このとき, $i=1,2, \dots, N$ に対して, $i$ 行目に以下を出力せよ.

頂点 $i$ の近傍を昇順に $x_{i,1}, \dots, x_{i,d_i}$ とする.
このとき, $d_i, x_{i,1}, \dots, x_{i,d_i}$ の順に出力する.

制約

$1 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq A_i \lt B_l \leq N$
$G$ は単純無向グラフ

解法

出力すべきは $G$ の隣接リストである. よって, 実際に与えられる無向グラフを隣接リストで保存していき, $i=1,2, \dots, N$ の順に各リストの長さとその要素を出力すれば良い. ただし, 各リストを昇順にソートすることを忘れずに.