AT_abc343_b [ABC343B] Adjacency Matrix

题目描述

有一个包含 $N$ 个顶点的简单无向图 $G$，图中的顶点编号为 $1,2,\ldots,N$。

给定 $G$ 的邻接矩阵 $(A_{i,j})$。也就是说，当且仅当 $A_{i,j}=1$ 时，顶点 $i$ 和顶点 $j$ 之间有一条边。

对于 $i=1,2,\ldots,N$，请按升序输出与顶点 $i$ 直接相连的顶点编号。

这里，顶点 $i$ 和顶点 $j$ 直接相连，指的是存在一条连接顶点 $i$ 和顶点 $j$ 的边。

输入格式

输入以如下格式从标准输入读入。

$N$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,N}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,N}$

输出格式

输出 $N$ 行。第 $i$ 行请按升序、用空格分隔输出与顶点 $i$ 直接相连的所有顶点编号。

输入输出样例 #1

输入 #1

4
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0

输出 #1

2 3
1 4
1
2

输入输出样例 #2

输入 #2

2
0 0
0 0

输出 #2

输入输出样例 #3

输入 #3

5
0 1 0 1 1
1 0 0 1 0
0 0 0 0 1
1 1 0 0 1
1 0 1 1 0

输出 #3

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

说明/提示

限制条件

• $2 \leq N \leq 100$
• $A_{i,j} \in \{0,1\}$
• $A_{i,i} = 0$
• $A_{i,j} = A_{j,i}$
• 所有输入的值均为整数

样例解释 1

与顶点 $1$ 直接相连的顶点为 $2,3$。因此，第 $1$ 行输出 $2,3$，顺序为升序。同理，第 $2$ 行输出 $1,4$，第 $3$ 行输出 $1$，第 $4$ 行输出 $2$。

样例解释 2

图 $G$ 也有可能没有任何边。

由 ChatGPT 4.1 翻译