9086:求连通分量

Time/Memory Limit:1000 MS/32768 K
Submitted: 453 Accepted: 316

 Problem Description

设有一无向图,其顶点值为字符型并假设各值互不相等,采用邻接矩阵表示法存储表示。利用BFS算法求其各连通分量,并按广度优先遍历的顺序输出各连通分量中的顶点(若该无向图为连通图,则做为一个连通分量)。

 Input

有多组测试数据,每组数据的第一行为两个整数n和e,表示n个顶点和e条边(1<n<20);第二行为其n个顶点的值,按输入顺序进行存储;后面有e行,表示e条边的信息,每条边信息占一行,包括边所依附的顶点下标i和j,数据之间用空格隔开。

 Output

每组输出数据占若干行,每行输出一个连通分量中的顶点(若该无向图为连通图,则做为一个连通分量),要求按广度优先遍历的顺序输出各顶点,每两组输出数据之间有一空行,具体格式见样例。

 Sample Input

4 4
ABCD
0 1
0 3
1 2
1 3

4 3
ABCD
0 1
0 3
1 3

 Sample Output

1:A,B,D,C

1:A,B,D
2:C

 Author

hwt

 Recommend

zh