Module: Suche in die Tiefe. DFS


Problem

5 /12


Zweifarbiger Graph

Theory Click to read/hide

Dwood Count
Dwood Count - eine Reihe, deren Spitzen in zwei Multipliken zerbrochen werden können, so dass jede Rippe die Oberseiten verschiedener Multiplikationen verbindet.


Das Konzept wird häufig im Kontext von Doppel-Doppel-Diagrammen verwendetFarbeOben. Die Aufteilung der Zählung in zwei Proportionen wird genanntUkraineSein Top ist zwei verschiedene Farben. Jede Rippe muss die Oberseiten verschiedener Farben verbinden.

Um die Doppeldoppelung zu überprüfen und die Probe nach Maß zu kalibrieren, am häufigsten verwendet DFS♪

Algorithmen

Beginnen wir eine Farbe mit einer beliebigen Spitze, die in einer beliebigen Farbe lackiert ist.
Wenn wir durch jede Rippe gehen, malen wir das nächste Top in der entgegengesetzten Farbe.
Wenn wir einen Peak von benachbarten Peaks gefunden haben, die bereits in der gleichen Farbe wie die aktuelle, gibt es einen ungeraden Zyklus in der Zählung, was bedeutet, dass es nicht zwei-Wege ist.

Problem

Der Graph wird als zweifarbig bezeichnet, wenn seine Eckpunkte in zwei Farben gemalt werden können, sodass keine Kanten die Eckpunkte der gleichen Farbe verbinden (dh jede Kante geht vom Eckpunkt der ersten Farbe zum Eckpunkt der zweiten Farbe).
Der Graph ist gegeben. Es muss überprüft werden, ob es sich um ein zweiteiliges Objekt handelt, und wenn ja, malen Sie die Eckpunkte.
 
Eingabe
In der ersten Zeile wird zuerst die Zahl N angegeben - die Anzahl der Eckpunkte des Graphen (nicht größer als 100). Als nächstes kommt die Adjazenzmatrix - eine Matrix mit der Größe NxN von 0 und 1 (0 steht für das Fehlen einer Kante, 1 für das Vorhandensein). Der Graph ist nicht ausgerichtet, ohne Schleifen.
 
Ausgabe 
Geben Sie in der ersten Zeile eine der YES - oder NO -Meldungen aus (je nachdem, ob das Diagramm zweideutig ist oder nicht). Wenn YES antwortet, Geben Sie in der zweiten Zeile N von Zahlen aus - die Farben, in die die Eckpunkte eingefärbt werden sollen: Verwenden Sie für die erste Farbe den Wert 1, für die zweite Farbe den Wert 2. Der erste Scheitelpunkt sollte die Farbe 1 haben.
 
Beispiele
№ Eingabe Ausgabe
1
3
0 1 1
1 0 1
1 1 0
 NO
2
3
0 1 1
1 0 0
1 0 0
YES
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!