请编写程序,用广度优先搜索输出给定无向图中的各个连通分量。
注意输出顺序规定如下:
- 每个连通分量的输出从其中编号最小的顶点开始;
- 不同连通分量按其第一个顶点的编号增序输出,每个连通分量占一行;
- 当一个顶点有多个邻接点时,按其输入的逆序进行访问,即最后输入的邻接点,在广度优先搜索中应被最先访问输出。
输入格式:
输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex
(≤10)。
第二行给出两个正整数,依次为当前要创建的图的顶点数 n 和边数 m(保证顶点数至少为 2 且不超过最大顶点数量)。
第三行给出 n 个英文字母,顺序对应每个顶点的信息。
随后 m 行,每行给出一条无向边的两个端点的编号、以及边的权重。顶点编号从 0 开始,权重(≤230)为整数。
同行数字、字符均以一个空格分隔。
输出格式:
按照题面中规定的顺序,输出图中的连通分量每个顶点的信息。每个连通分量占一行,字符间不要有空格。
输入样例:
10
6 7
a b c d e f
2 0 2
2 3 1
3 0 3
3 4 4
2 4 2
4 0 5
4 5 1
输出样例:
aedcf
b