Am 31.07.2017 um 10:58 schrieb tomas@tuxteam.de:
On Mon, Jul 31, 2017 at 10:28:42AM +0200, Urs Liska wrote:
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?
Erstmal herzlichen Dank dafür - das ist genau das, was ich brauche (nicht fertige Lösungen). Aber Deine Eingabe passt irgendwie nicht. Nach den Vorgaben sagt dieser: 5 Knoten und 5 Verbindungen, es folgen aber nur vier Verbindungen.
Öh -- ja. Ups. Pfui. Schlamperei.
Wenn ich die fünf Knoten mit vier Verbindungen zeichne, kommt das
heraus:
1-2 3---5 \ / 4
also ein Graph mit zwei nicht verbundenen Teilen. Ist es das, was du
meinst?
Genau.
Na, dann war deine unvollständige Eingabe immerhin vollständig genug, um das Problem zu verdeutlichen.
Wenn solche geteilten Graphen als Eingabe erlaubt sind, dann scheitert mein Code daran, dass er beim ersten Knoten anfängt und daher nur einen Teilgraphen absucht.
Exakt. Der Graph muss nicht zusammenhängend ("connected") sein. Zumindest steht in der Aufgabenstellung nichts darüber.
Das wäre möglich, aber normalerweise finden sich inden Instruktionen doch irgendwelche Hinweise auf solche zu beachtenden Details. Ich werde mal im Forum nachfragen und sehen, ob ein Mentor etwas dazu sagt.
Hm. Das ist eine interessante Feststellung: jedes Gebiet hat so etwas wie "implizites Wissen", Dinge, "über die man nicht sprechen muss", und ein Teil der Mühen, sich das zu erarbeiten ist, dieses zu lernen.
Ist ein Graph immer zusammenhängend, es sei denn, man wird extra darauf hingewiesen? Wie ich die Graph-Fuzzis so kenne: nein.
Ja, das ist das Eine. Das Andere ist, wie man so etwas in einem Kurs handhabt. Das Konzept des bipartiten Graphen war vorher nicht in den Lektionen drangekommen, sondern in dieser Aufgabe zum ersten Mal beschrieben. Insofern ist die Erwartung, dass man selbst drauf kommt, relativ hoch gesteckt. Immerhin ist dieser (mein) Denkfehler sogar auf Wikipedia zu finden: https://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness beschreibt genau, was ich gemacht hatte. Ich denke, das könnte eine kleine Ergänzung vertragen ...
Ah doch. Die "Constraints" sagen: 1 <= n <= 10^3 Knoten und 0 <= m <= 10^4 Verbindungen. Das heißt, Graphen mit Knoten und *keinen* Verbindungen sind erlaubt.
Das o.a. Beispiel hat aber auch noch Knoten & Verbindungen, ist nur "nicht zusammenhängend".
Knoten *ohne* Verbindungen sind bipartit, denn es geht nicht darum, dass "zweifarbige" Verbindungen da sein müssen, sondern darum, dass *vorhandene* Verbindungen zweifarbig sein müssen.
Der Bug müsste demnach sein, dass ich sicherstellen muss, dass alle Knoten besucht worden sind. Darüber hinaus könnte ich direkt abbrechen, wenn der Graph keine Verbindungen hat, was bei den Sonderfällen viel Zeit sparen kann.
Zum einen, ja. Aber auch:
1 -- 2 3 -- 4
ist bipartit. Dein Code würde auch "ja" sagen, aber in der Hälfte der Zeit, die er eigentlich dazu bräuchte :-)
Entweder blamiere ich mich jetzt, oder Du findest einen Bug :^)
Oder beides, s.o.
Ich werde der Sache nachgehen ;-)
Enjoy
Das war's übrigens - jetzt wurde die Lösung akzeptiert. Also auf zu neuen Problemen ...
Herzlichen Dank nochmal Urs
-- t