-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
Bei der Frage, ob ein Graph bipartit ist, scheitere ich an einer "falschen Antwort". Hier muss ich sagen, dass mir die Implikationen der Aufgabe noch etwas schwammit sind und mein Ansatz daher vielleicht zu naiv ist.
?
Ich suche per Breitensuche nach erreichbaren Knoten und färbe alle Nachbarn eines Knotens mit der "anderen" Farbe ein. Wenn ich auf einen Knoten stoße, der bereits entdeckt wurde, aber dieselbe Farbe wie ein aktueller Knoten hat, erkenne ich den Graphen als nicht bipartit.
Sieht korrekt aus, auch lesbar. Daher mein Fragezeichen da oben. Dem Code nach zu urteilen hast Du verstanden, worum es geht.
Bei allen angegebenen Beispiel-Eingaben funktioniert das auch, aber der Grader weist einen (mir unbekannten) Test-Fall ab.
Probier mal das:
5 5 1 2 3 4 4 5 5 3
Ist nicht bipartit. Dein Code wird aber (ich riskiere eine Blamage: ich habe es nicht getestet!) behaupten, es sei bipartit. Was fehlt noch?
Entweder blamiere ich mich jetzt, oder Du findest einen Bug :^)
lg - -- t