102761: [AtCoder]ABC276 B - Adjacency List

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:9 Solved:0

Description

Score : $200$ points

Problem Statement

There are $N$ cities numbered $1, \dots, N$, and $M$ roads connecting cities.
The $i$-th road $(1 \leq i \leq M)$ connects city $A_i$ and city $B_i$.

Print $N$ lines as follows.

  • Let $d_i$ be the number of cities directly connected to city $i \, (1 \leq i \leq N)$, and those cities be city $a_{i, 1}$, $\dots$, city $a_{i, d_i}$, in ascending order.
  • The $i$-th line $(1 \leq i \leq N)$ should contain $d_i + 1$ integers $d_i, a_{i, 1}, \dots, a_{i, d_i}$ in this order, separated by spaces.

Constraints

  • $2 \leq N \leq 10^5$
  • $1 \leq M \leq 10^5$
  • $1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)$
  • $(A_i, B_i) \neq (A_j, B_j)$ if $(i \neq j)$.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

Output

Print $N$ lines as specified in the Problem Statement.


Sample Input 1

6 6
3 6
1 3
5 6
2 5
1 2
1 6

Sample Output 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

The cities directly connected to city $1$ are city $2$, city $3$, and city $6$. Thus, we have $d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6$, so you should print $3, 2, 3, 6$ in the first line in this order, separated by spaces.

Note that $a_{i, 1}, \dots, a_{i, d_i}$ must be in ascending order. For instance, it is unacceptable to print $3, 3, 2, 6$ in the first line in this order.


Sample Input 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 2

4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4

Input

题意翻译

+ 给定一张 $n$ 点 $m$ 边的双向图。 + 你需要输出一张邻接表,按照邻居编号单调递增存储。 ### 输出格式: 第 $k$ 行输出 $k$ 号点的邻居编号。 先输出 $k$ 号点的邻居个数,再按照升序输出 $k$ 号点的所有邻居。

Output

得分:200分

问题描述

有编号为$1, \dots, N$的$N$个城市,以及连接城市的$M$条道路。

第$i$条道路$(1 \leq i \leq M)$连接城市$A_i$和城市$B_i$。

按如下格式打印$N$行。

  • 令$d_i$表示与城市$i \, (1 \leq i \leq N)$直接相连的城市数量,这些城市为城市$a_{i, 1}$, $\dots$, 城市$a_{i, d_i}$,按升序排列。
  • 第$i$行$(1 \leq i \leq N)$应包含$d_i + 1$个整数$d_i, a_{i, 1}, \dots, a_{i, d_i}$,按此顺序用空格分隔。

约束

  • $2 \leq N \leq 10^5$
  • $1 \leq M \leq 10^5$
  • $1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)$
  • 若$(i \neq j)$,则$(A_i, B_i) \neq (A_j, B_j)$。
  • 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出:

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

输出

按问题描述中指定的格式打印$N$行。


样例输入 1

6 6
3 6
1 3
5 6
2 5
1 2
1 6

样例输出 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

与城市$1$直接相连的城市是城市$2$,城市$3$和城市$6$。因此,我们有$d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6$,所以您应该以以下顺序在第一行打印$3, 2, 3, 6$,用空格分隔。

注意$a_{i, 1}, \dots, a_{i, d_i}$必须按升序排列。例如,按顺序打印$3, 3, 2, 6$是不可接受的。


样例输入 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出 2

4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4

加入题单

上一题 下一题 算法标签: