曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5643: 图的深度优先遍历

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：33 Solved：9
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

对于给定的图G（邻接矩阵表示），和给定的顶点V，要求从顶点V出发遍历图G，输出符合条件的深度优先序列。



Input

第一行两个整数n和v，n表示图的顶点数（n<=100），v表示遍历的开始顶点；

接下来n行是图G的邻接矩阵。

Output

    一行输出以顶点v为起点的深度优先遍历序列，对于任一起点，首先遍历的是顶点序号最小的、尚未被访问的一条边。

Sample Input Copy 

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

Sample Output Copy 

1 2 3 4

HINT

连通图基于连通的概念。在一个无向图G中，若从顶点v_i到顶点v_j有路径相连（当然从v_j到v_i也一定有路径），则称v_i和v_j是连通的。如果G是有向图，那么连接v_i和v_j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。