Am 31.07.2017 um 09:10 schrieb tomas@tuxteam.de:
On Sat, Jul 29, 2017 at 09:49:21AM +0200,
Urs Liska wrote:
> 2)
> 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.
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?
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. Das wäre möglich, aber
normalerweise finden sich in den Instruktionen doch irgendwelche
Hinweise auf solche zu beachtenden Details. Ich werde mal im Forum
nachfragen und sehen, ob ein Mentor etwas dazu sagt.
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.
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.
Entweder blamiere ich mich jetzt, oder Du findest einen Bug :^)
Ich werde der Sache nachgehen ;-)
lg
-- t
> _______________________________________________
> Freiburger Linux User Group
> Mail an die Liste: flug@lug-freiburg.de
> Mailingliste verwalten (u.a. abbestellen): https://lug-freiburg.de/mailman/listinfo/flug
--
ul@openlilylib.org
https://openlilylib.org
http://lilypondblog.org