Module: Busca en profundidad. SFD


Problem

5 /12


gráfica bipartita

Theory Click to read/hide

Gráfico bipartito
 
Gráfico bipartito: un gráfico cuyos vértices se pueden dividir en dos conjuntos para que cada borde conecte el vértices de diferentes conjuntos.


A menudo, en el contexto de gráficos bipartitos, se utiliza el concepto de  colores vértices. Dividir un gráfico en dos partes se llama colorear sus vértices con dos colores diferentes. Cada borde debe conectar vértices de un color diferente.

DFS. 
 

Algoritmo

Comenzamos a pintar desde un vértice arbitrario, que pintamos en un color arbitrario.
Al pasar a lo largo de cada borde, pinte el siguiente vértice en el color opuesto.
Si, al iterar sobre los vértices vecinos, encontramos un vértice que ya está pintado del mismo color que el actual, entonces hay un ciclo impar en el gráfico, lo que significa que no es bipartito.

Problem

Un gráfico se llama bipartito si sus vértices se pueden colorear en dos colores para que no haya bordes que conecten vértices del mismo color (es decir, cada borde va desde el vértice del primer color hasta el vértice del segundo) .
Dada una gráfica. Se requiere verificar si es bipartito, y de ser así, colorear sus vértices.
 
Entrada
La primera línea primero contiene el número N - el número de vértices del gráfico (no excede 100). Luego viene la matriz de adyacencia: una matriz NxN de 0 y 1 (0 significa sin borde, 1 significa presencia). El gráfico no está dirigido, sin bucles.
 
Impresión 
En la primera línea imprima uno de los mensajes YES o NO (dependiendo de si el gráfico es bipartito o no). Si la respuesta es SI, en la segunda línea escribe números N - los colores para colorear los vértices: para el primer color usa el valor 1, para el segundo color: el valor 2. El primer vértice debe ser el color 1.
 
Ejemplos

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Entrada Salida
1
3
0 1 1
1 0 1
1 1 0
 NO
2
3
0 1 1
1 0 0
1 0 0
SÍ
1 2 2