Ziel - Um die minimale Wirbelabdeckung eines Baumes zu finden. Bei einem nicht gewichteten, ungerichteten Baum ist die minimale Wirbelabdeckung zu finden. Nachdem überprüft wurde, ob der Graph zweigeteilt ist oder nicht, und auch die 2 Scheitelpunkte gemacht wurden, ist es wahr, dass das Minimum dieser 2 Sätze die minimale Deckung liefert. Wenn ja, was scheint der Fehler im folgenden Code zu sein? Derselbe Code hat die unten erwähnte Frage in einem Codeforces-Wettbewerb erfolgreich bestanden, jedoch würde er ein WA geben, wenn er (mit leichten Änderungen wie bei der Eingabe) für das erwähnte Spoj-Problem verwendet wird.Minimale Scheitelpunktabdeckung des Baums
Und ja, offensichtliche Änderungen im Ausgabeformat wurden während der Einreichung auf Spoj gemacht.
Codeforces Frage zu überprüfen, ob Bipartit oder nicht.
http://www.codeforces.com/problemset/problem/688/C
Meine Vorlage
enter code herehttp://ideone.com/PwduxV
Frage zum SPOJ die Mindestdeckung zu finden.
http://www.spoj.com/problems/PT07X/
Bitte erläutern Sie das Problem genauer. Die Probleme sind sehr unterschiedlich; Das SPOJ-Problem ist "einfach" in dem Sinne, wie du es beschreibst, nämlich das Erzeugen einer 2-Färbung (die existiert, da Bäume zweigeteilt sind) und das Zurückgeben der kleineren Farbklasse. Das Codeforce-Problem verlangt jedoch die Erzeugung von zwei disjunkten Vertex-Cover eines beliebigen Graphen, von denen es nicht einmal garantiert ist, dass sie existieren (wie man anhand des vollständigen Graphen an 3 Knoten sehen kann). – Codor
Was Codeforces will, ist zu prüfen, ob der Graph zweigeteilt ist, wenn ja, dann drucken Sie die zwei disjunkten Sätze. Für spoj ist sichergestellt, dass es eine Zweiteilung gibt, da wir einen Baum bekommen haben. Wenn Sie also nur die 2 Sets als bei Codeforces gefunden und das mit der kleineren Größe drucken würden, würde das nicht ausreichen? –
Das ist ziemlich aufschlussreich; meinen Sie, dass in der Codeforce-Formulierung die beiden Vertex-Cover die Partitionen wären, was beweisen würde, dass der Input zweigeteilt ist? Wenn dies der Fall ist, ist das Titelproblem "NP" sehr irreführend. – Codor