编程题:一笔画基础
判断某图能否一笔画出的问题称为一笔画问题。对于图中的某个顶点,它所拥有的边数称为它的度。若某顶点的度为奇数,则该顶点称为奇点,否则称为偶点。若某图的所有顶点都为偶点或仅有两个奇点,则该图必可一笔画出。
这里是一个一笔画的基础问题,对于有向图(每条边都有方向),要求按从小到大的顺序输出所有偶点的编号(从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
答案:若无答案欢迎评论
这里是一个一笔画的基础问题,对于有向图(每条边都有方向),要求按从小到大的顺序输出所有偶点的编号(从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
答案:若无答案欢迎评论