[PYTHON] [Competition Pro Struggle] Implementierte Union Find

Motivation

Ich bin ein schwacher Programmierer, aber ich habe beschlossen, wettbewerbsfähig zu programmieren, um ein starker Programmierer zu werden. Wie Sie sehen können, wenn Sie es versuchen, erinnern Sie sich oft daran. Ich denke, dass ich Mathematik in der Prüfung löse, aber natürlich ist Denkfähigkeit wichtig, aber um die Antwort in kurzer Zeit in der eigentlichen Prüfung zu erreichen, ist es auch wichtig, viele Rückzüge zu haben.

Daher werden wir die wichtigsten Algorithmen und Datenstrukturen nacheinander implementieren.

Dieses Mal, das erste Mal, werden wir eine Datenstruktur namens Union Find implementieren.

Übrigens, da die Motivation für konkurrierende Profis darin besteht, effizient Geschäfte zu machen, werde ich meine Lieblingssprache Python anstelle von C ++ verwenden, die von allen konkurrierenden Profis anstelle von Po ** Hub verwendet wird. (Ich habe in einem Artikel gesehen, dass C ++ viermal schneller ist, aber viermal ist ein Fehler, nicht wahr?)

UnionFind Union Find ist, wenn N Knoten in Gruppen unterteilt sind

1. Verbinden Sie die Gruppen, zu denen zwei beliebige Knoten a und b gehören, zu einer Gruppe.
2. Stellen Sie fest, ob zwei Knoten a und b zur selben Gruppe gehören Eine auf die Funktion spezialisierte Datenstruktur.

Beides kann mit dem Einlaufberechnungsbetragsprotokoll (N) implementiert werden.

Algorithmus

Alle Bilder stammen von Nice slide

Implementierung

Datenstruktur

Schwache Programmierer wissen nicht, wie sie zuerst Daten speichern sollen, aber UnionFind ist eine ** Baumstruktur, die sich ** daran erinnert, wer der übergeordnete Knoten ist. Wenn Sie also n Knoten ** gruppieren möchten, benötigen Sie nur eine Liste, die die Eltern jedes Knotens ** enthält.

class UnionFind:
    def __init__(self, n):
        self.parents = list(range(n))
    ...

Da der Wurzelknoten kein übergeordnetes Element hat, ** drückt das übergeordnete Element es übrigens als seinen eigenen Knoten = Stammknoten aus. ** **. Zunächst sind sie alle Stammknoten, da sie als separate Gruppen initialisiert werden.

Beurteilung

    def is_united(self, x, y):
        return self._root(x) == self._root(y)

Wie Sie in dem Bild sehen können, das von der schönen Folie zitiert wird, müssen Sie nur feststellen, ob die Wurzelknoten gleich sind. Verwenden Sie also die _root-Methode, um die Wurzelknoten zu ziehen und zu vergleichen, ob sie gleich sind. Das ist gut.

Beim Schreiben von Code denke ich, dass es am einfachsten ist, den gesamten Algorithmus schnell zu schreiben, indem man denkt, dass es bereits eine abgeschlossene Funktion für den detaillierten Subalgorithmus gibt.

Wenn Sie 3 Minuten lang nicht gekocht hätten und gesagt hätten: "Heute habe ich eine geräucherte Kartoffel, die hier hergestellt wurde", könnte ich nicht das ganze Bild des Gerichts sehen.

Beitreten

    def union(self, x, y):
        self.parents[self._root(y)] = self._root(x)

Dies ist auch so, wie es auf einer schönen Folie geschrieben ist. Wenn Sie die Gruppe von x und die Gruppe von y kombinieren möchten, müssen Sie nur einen der Wurzelknoten an den Wurzelknoten des anderen anhängen.

Selbst wenn Sie zum Anhängen sagen, geben Sie einfach das übergeordnete Element des Knotens an, an den Sie eine Verbindung zu dem Knoten herstellen möchten, an den eine Verbindung hergestellt werden soll.

Holen Sie sich den Wurzelknoten

Der einzige Subalgorithmus, den ich bisher verwendet habe, ist "_root", daher sollte die Implementierung abgeschlossen sein.

    def _root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root = self._root(self.parents[x])
            return root

Um den Stammknoten zurückzugeben, müssen Sie nur dann zum übergeordneten Knoten zurückkehren, bis ein Knoten angezeigt wird, in dem der übergeordnete Knoten selbst angezeigt wird. Die UnionFind-Baumdatenstruktur ist einfach, da sie sich auf das übergeordnete Element jedes Knotens bezieht.

Auf einer großen Folie stand jedoch, dass der Rechenaufwand geringer wäre, wenn die Baumstruktur aufgrund des Rechenaufwands so flach wie möglich wäre.

Also werde ich dem Code etwas Einfallsreichtum hinzufügen.

    def _root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root = self._root(self.parents[x])
            self.parents[x] = root  #Stellen Sie die direkte Verbindung zum übergeordneten Knoten wieder her.
            return root

Damit ist Union Find abgeschlossen!

Versuche dich zu bewegen

uf = UnionFind(5)
uf.union(0, 3)
uf.union(1, 3)
print(uf.is_united(0, 1))  # True

Das Ende

Ich suche einen Begleiter, der als Ingenieur hart zusammenarbeitet. Ich würde mich sehr freuen, wenn Sie LGTM, Follow und Twitter folgen.