Preparing NOJ

图的宽度优先遍历序列

1000ms 65536K

Description:

(graph)是数据结构 G=(V,E),其中VG中结点的有限非空集合,结点的偶对称为边(edge)EG中边的有限集合。设V={0,1,2,……,n-1},图中的结点又称为顶点(vertex),有向图(directed graph)指图中代表边的偶对是有序的,用<uv>代表一条有向边(又称为弧),则u称为该边的始点(尾),v称为边的终点(头)。无向图(undirected graph)指图中代表边的偶对是无序的,在无向图中边(uv )(vu)是同一条边。

输入边构成无向图,求以顶点0为起点的宽度优先遍历序列。

Input:

第一行为两个整数ne,表示图顶点数和边数。以下e行,每行两个整数,表示一条边的起点、终点,保证不重复、不失败。1n200e190

Output:

前面n行输出无向图的邻接矩阵,最后一行输出顶点0为起点的宽度优先遍历序列,对于任一起点,按终点序号从小到大的次序遍历每一条边每个序号后输出一个空格。

Sample Input:

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

Sample Output:

0 1 0 1 
1 0 1 1 
0 1 0 1 
1 1 1 0 
0 1 3 2 

Note:

本题由旧版NOJ导入,来源:CHENZ

Info

NOJ

Provider NOJ

Code NOJ1048

Tags

Submitted 349

Passed 111

AC Rate 31.81%

Date 04/20/2019 10:03:10

Related

Nothing Yet