Module: Pesquise em profundidade. DFS


Problem

5 /12


gráfico bipartido

Theory Click to read/hide

Gráfico bipartido
 
Gráfico bipartido - um gráfico cujos vértices podem ser divididos em dois conjuntos de modo que cada aresta conecte o vértices de diferentes conjuntos.


Freqüentemente, no contexto de grafos bipartidos, o conceito de cores vértices é usado. A divisão de um grafo em duas partes é chamada colorir seus vértices com duas cores diferentes. Cada aresta deve conectar vértices de uma cor diferente.

DFS. 
 

Algoritmo

Começamos a pintar a partir de um vértice arbitrário, que pintamos com uma cor arbitrária.
Ao passar por cada aresta, pinte o próximo vértice na cor oposta.
Se, ao iterar sobre os vértices vizinhos, encontrarmos um vértice já pintado da mesma cor do atual, então há um ciclo ímpar no grafo, o que significa que ele não é bipartido.

Problem

Um grafo é dito bipartido se seus vértices podem ser coloridos em duas cores de forma que não existam arestas conectando vértices da mesma cor (ou seja, cada aresta vai do vértice da 1ª cor ao vértice da 2ª) .
Dado um gráfico. É necessário verificar se é bipartido e, em caso afirmativo, colorir seus vértices.
 
Entrada
A primeira linha contém primeiro o número N - o número de vértices do grafo (não excede 100). Em seguida, vem a matriz de adjacência - uma matriz NxN de 0 e 1 (0 significa sem borda, 1 significa presença). O grafo é não direcionado, sem loops.
 
Impressão 
Na primeira linha imprima uma das mensagens YES ou NO (dependendo se o grafo é bipartido ou não). Se a resposta for SIM, na segunda linha imprima N números - as cores para colorir os vértices: para a primeira cor use o valor 1, para a segunda cor - o valor 2. O primeiro vértice deve ser a cor 1.
 
Exemplos
# Entrada Saída
1
3
0 1 1
1 0 1
1 1 0
 NÃO
2
3
0 1 1
1 0 0
1 0 0
SIM
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!