-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Mon, Jul 31, 2017 at 10:28:42AM +0200, Urs Liska wrote:
Am 31.07.2017 um 09:10 schrieb tomas@tuxteam.de:
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?
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.
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.
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 - -- t