Module: Cerca in profondità. DFS


Problem

5 /12


grafico bipartito

Theory Click to read/hide

Grafico bipartito
 
Grafico bipartito - un grafico i cui vertici possono essere divisi in due insiemi in modo che ciascun bordo colleghi il vertici da insiemi diversi.


Spesso nel contesto dei grafici bipartiti, viene utilizzato il concetto di colori vertici. Dividere un grafico in due parti si chiama colorare i suoi vertici con due colori diversi. Ogni bordo deve collegare i vertici di un colore diverso.

DFS. 
 

Algoritmo

Iniziamo a dipingere da un vertice arbitrario, che dipingiamo con un colore arbitrario.
Quando passi lungo ogni bordo, dipingi il vertice successivo con il colore opposto.
Se, durante l'iterazione sui vertici vicini, troviamo un vertice che è già dipinto dello stesso colore di quello attuale, allora c'è un ciclo dispari nel grafico, il che significa che non è bipartito.

Problem

Un grafo si dice bipartito se i suoi vertici possono essere colorati in due colori in modo che non ci siano spigoli che collegano vertici dello stesso colore (ovvero ogni spigolo va dal vertice del 1° colore al vertice del 2°) .
Dato un grafico. È necessario verificare se è bipartito e, in tal caso, colorare i suoi vertici.
 
Input
La prima riga contiene prima il numero N - il numero di vertici del grafico (non supera 100). Poi viene la matrice di adiacenza - una matrice NxN di 0 e 1 (0 significa nessun bordo, 1 significa presenza). Il grafico è non orientato, senza loop.
 
Impronta 
Sulla prima riga stampa uno dei messaggi YES o NO (a seconda che il grafico sia bipartito o meno). Se la risposta è SI, nella seconda riga stampa N numeri - i colori per colorare i vertici: per il primo colore usa il valore 1, per il secondo colore - il valore 2. Il primo vertice dovrebbe essere di colore 1.
 
Esempi
# Input Uscita
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

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!