← Volver a los ejercicios

UVa 10004, Bicoloring: el coloreo en profundidad sobre los casos del juez

El código de bipartito corre sobre la muestra del juez y sobre dos casos más. En cada paso usted decide el color del nodo o qué pasa con la arista, y al final de cada caso, qué imprime el programa. Una respuesta equivocada dice qué se miró mal y se puede volver a intentar.
Enunciado y envío: https://vjudge.net/problem/UVA-10004. La página pide cuenta para ver el enunciado.

1. Lo que pide el juez

Cada caso trae n, con 1 < n < 200, los nodos 0 a n − 1, luego el número l de aristas y l líneas con dos nodos cada una. El grafo es no dirigido, sin lazos y conexo. Por cada caso se imprime BICOLORABLE. si los nodos se pueden pintar con dos colores sin que una arista una dos del mismo color, y NOT BICOLORABLE. si no. La entrada termina con n = 0.

Entrada de muestra

Salida de muestra

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

2. El código sobre cada caso

Se abre al terminar las preguntas.

Entrada del caso

Borde negro: el nodo u de la llamada de arriba. Arista ámbar: la que se está mirando. Arista roja: un choque.

En este caso, ¿cuántas veces corrió la línea 4, if color[v] == -1?

3. Si el grafo no fuera conexo

Se abre al terminar las preguntas.

Como el juez promete un grafo conexo, alguien envía una versión que reemplaza el ciclo de afuera por una sola llamada pintar(adj, color, 0, 0). Esta entrada no cumple la promesa.

Al terminar esa llamada, ¿cuántos nodos siguen con color = -1?

4. Para resolver sin ayuda

Se abre al terminar las preguntas.

Escriba la entrada de un caso conexo con n = 8 y 10 aristas cuya salida sea NOT BICOLORABLE., y en el que quitar una sola arista, sin desconectar el grafo, cambie la salida a BICOLORABLE.. Diga cuál es esa arista y cuántas veces corre la línea 4 antes y después de quitarla.