本题请你编写程序,输出给定无向连通图中的割点和割边。
输入格式:
输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex
(≤20)。
第二行给出两个正整数,依次为当前要创建的图的顶点数 n 和边数 m(保证顶点数至少为 2 且不超过最大顶点数量)。
第三行给出 n 个小写英文字母,其间以 1 个空格分隔,顺序对应每个顶点的信息。
随后 m 行,每行给出一条无向边的两个端点的编号。顶点编号从 0 开始,编号间以 1 个空格分隔。
题目保证没有边被重复给出,并且图一定是连通的。
输出格式:
首先在一行中输出所有割点的字母信息,中间不要空格。如果没有割点则输出一个空行。
随后每行按格式 (v1, v2)
输出一条割边,其中 v1
和 v2
为割边两端点的字母信息。如果没有割边则不要输出任何信息。
输入样例:
20
10 11
a b c d e f g h i j
0 1
1 2
1 3
2 4
3 4
3 5
5 6
5 7
6 7
7 8
7 9
输出样例:
bdfh
(b, a)
(d, f)
(h, i)
(h, j)
注意:割点和割边的输出顺序是不唯一的,以任何顺序输出都可以,有特殊裁判程序判断输出的正确性。例如下列输出也是正确的。
hbdf
(d, f)
(h, i)
(a, b)
(h, j)