-->
当前位置:首页 > 题库

编程题:一笔画基础

Luz4年前 (2022-10-27)题库336
判断某图能否一笔画出的问题称为一笔画问题。对于图中的某个顶点,它所拥有的边数称为它的度。若某顶点的度为奇数,则该顶点称为奇点,否则称为偶点。若某图的所有顶点都为偶点或仅有两个奇点,则该图必可一笔画出。

这里是一个一笔画的基础问题,对于有向图(每条边都有方向),要求按从小到大的顺序输出所有偶点的编号(从1开始)。有向图以邻接矩阵A存储,若顶点i到顶点j有边,则矩阵元素A[i][j]的值为1,否则A[i][j]的值为0,此时某顶点所在行和列中1的个数就是该顶点的度。例如,样例1中顶点1的度为4,顶点2的度为5。

### 输入格式:

首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。对于每组测试,先输入一个正整数n(2≤n≤20),再输入一个n阶方阵(每个元素或为1或为0),表示有向图的邻接矩阵。

### 输出格式:

对于每组测试,输出一行,若该有向图不含偶点,则输出“none”(引号不必输出),否则按从小到大的顺序依次显示有向图中所有偶点的编号(从1开始),每两个数据之间留一个空格。

### 输入样例:

in
2
5
0 1 0 1 0
0 0 1 1 1
1 0 0 1 0
1 1 1 0 1
0 0 1 1 0
4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0



### 输出样例:

out
1 4 5
none








答案:若无答案欢迎评论