Trimestre 2013 Otoño
Entrega: 31 de octubre de 2013
Sea G = (V, E) una gráfica. Se dice que G es bipartita si se puede dividir V
en
dos subconjuntos A y B tales que no existe ninguna arista entre dos
vértices de A ni ninguna arista entre dos vértices de B
(dicho de otra forma, todas las aristas de G están entre un
vértice en A y un vértice en B). Se puede demostrar que G
es bipartita si y sólo si no
contiene un ciclo de longitud impar.
Escribe un programa bipartitaNN.c
que decida si una gráfica es bipartita o no, donde NN son los dos
dígitos de la
clave que le fue proporcionada por el profesor.
La entrada al programa consiste de un
renglón con dos enteros N y M (la cantidad de vértices y
aristas de G, respectivamente) seguido de M renglones con dos
enteros
Xj y Yj (las aristas de G). Puedes suponer que los vértices de G
están numerados del 1 al N y que 2 <= N <= 100.
La salida del programa consiste de un
renglón con un entero R (1 si G es bipartita y 0 si no lo es).
En el caso de que R sea bipartita
el segundo renglón deberá contener la cantidad P de
vértices en A y el tercer renglón deberá contener
una lista con los P vértices en A (ordenados de menor a mayor).
En el caso de que R no sea
bipartita
el segundo renglón deberá contener la longitud L de un
ciclo impar C de G y el tercer renglón deberá contener
una lista con los L vértices de C (en el orden en el que
aparezcan en el ciclo).
Entrada 1
Salida 1
Entrada 2
Salida 2
5 6
1 3
4 2
4 5
1 4
2 3
3 5
1
3
1 2 5
5 6
1 3
4 2
1 5
4 1
2 3
3 5
0
3
1 3 5
Observe que en el primer ejemplo también se pudo responder con P
= 2 y A = {3, 4} y que en el segundo ejemplo también se pudo
responder con L = 5 y C = (1, 4, 2, 3, 5). En general, para cada
gráfica G la respuesta R siempre es la misma, pero el resto de
la respuesta puede tener varias opciones. Para esta tarea basta que
dé cualquier respuesta correcta.
Idea: esta tarea se puede resolver con búsqueda en amplitud
o con búsqueda en profundidad.