URI Online Judge | 1082

Componentes Conectados

Por Neilor Tonin, URI Brazil

Límite de Tiempo: 1

Basado en estas tres definiciones:

Grafo conectado: Un grafo G (V, E) está conectado si para cada par de nodos u y v hay un camino entre u y v. Un grafo con un solo componente es un grafo conectado.

Grafo desconectado: Un grafo G (V, E) está desconectado si está formado por 2 o más componentes conectados.

Componente conectado: Los componentes conectados de un grafo son subgrafos conectados de ese grafo.

El siguiente grafo tiene 3 componentes conectados. El primero está formado por los nodos a, b, c. El segundo está formado sólo por el nodo d, y el tercer componente está formado por los nodos e y f.


Basándose en estos conceptos, donde cada entrada tiene identificación de cada uno de los vértices, aristas y los enlaces entre los nodos por las aristas, lista todos los componentes conectados que existen en el grafo, de acuerdo con la entrada dada.

Entrada

La primera línea del archivo de entrada contiene un entero N que representa el número de casos de prueba que siguen. Cada caso de prueba contiene 2 números V y E, respectivamente el número de Vértices(V) y Aristas(E) del grafo. Las siguientes E líneas, cada una representa una de las aristas que conectan tal vértice. Cada vértice está representado por una letra minúscula del alfabeto. Esto significa 26 vérticos como máximo (a-z). Cada grafo tiene al menos un componente conectado.

Observación: El vértice de cada caso de prueba comienza siempre con 'a'. Esto significa que un caso de prueba con 3 vértices tiene el vértice 'a', 'b' y 'c'.

Salida

Para cada caso de prueba, imprima el mensaje Caso #n: indicando el número de caso de prueba (como se muestra a continuación). Seguido el vértice de cada segmento, un segmento por linea, separado por comas (incluyendo una coma al final de la línea). Finalizado el caso de prueba se debe imprimir un mensaje indicando el número de componentes conectados del grafo. Cada caso de prueba debe tener una línea en blanco impresa al final, incluyendo la última.


Importante: Los vértices deben imprimirse en orden ascendente y si existe un arco de a a b significa que existe un arco de b a a.
Ejemplo de entrada Ejemplo de salida

3
3 1
a c
10 10
a b
a c
a g
b c
c g
e d
d f
h i
i j
j h
6 4
a b
b c
c a
e f

Case #1:
a,c,
b,
2 connected components

Case #2:
a,b,c,g,
d,e,f,
h,i,j,
3 connected components

Case #3:
a,b,c,
d,
e,f,
3 connected components