5691 - 图的深度优先遍历

读入一个用邻接矩阵存储的无向图,输出它的宽度优先遍历序列。

输入

第1行1个正整数n,表示图中顶点数,2≤n≤100;

接下来的n行是一个n*n的邻接矩阵,a[i][j]=1表示顶点i和顶点j之间有直接边相连,a[i][j]=0表示没有直接边相连。保证i=j时,a[i][j]=0,并且a[i][j]=a[j][i]。

输出

输出1~n的某一种排列,表示从顶点1开始,对该图进行深度优先遍历得到的顶点序列,每两个数之间用一个“-”分隔。

样例

输入

8
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 0 1 1
0 1 0 0 0 1 0 0
0 1 0 0 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 0

输出

1-2-4-6-5-3-7-8

来源

课课通

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题