ist. Mit anderen Worten, zum Zeitpunkt der Initialisierung gehören alle Elemente zur "Gruppe der Größe 1 mit Ihnen als Anführer (Gruppe mit Ihren eigenen Elementen)".

2.2. Find Die Operation Suchen wird in ACL unter dem Namensleiter implementiert. Durch Angabe eines Elements gibt diese Methode den Anführer der Gruppe zurück, zu der das Element gehört.

def leader(self, a):
    assert 0 <= a < self._n
    if self.parent_or_size[a] < 0: return a  #Leader wenn negativ
    self.parent_or_size[a] = self.leader(self.parent_or_size[a])
    return self.parent_or_size[a]

Erstens, wenn "parent_or_size [a]" in der dritten Zeile negativ ist, ist a der Anführer und kehrt so zurück, wie er ist. Andernfalls ist parent_or_size [a] der Anführer ** (vorläufig) ** von a. Dies liegt daran, dass ein Leiter bei einer Gruppenintegration kein Leiter mehr ist. Daher suchen wir rekursiv nach einem ** wahren ** Anführer dieses Lesers (vorläufig). Die Leserinformationen werden aktualisiert, indem die rechte Seite in die 4. Zeile eingesetzt wird, ohne direkt zurückzukehren. Es kann gesagt werden, dass es in ein Memo gemacht wird. Dies verkürzt die nächste und nachfolgende Suche.

2.3. Union Die Operation Union wird in ACL unter dem Namen Merge implementiert. Diese Methode integriert die Gruppen, zu denen sie gehören, indem zwei Elemente angegeben werden.

def merge(self, a, b):
    assert 0 <= a < self._n
    assert 0 <= b < self._n
    x, y = self.leader(a), self.leader(b)
    if x == y: return x
    if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
    self.parent_or_size[x] += self.parent_or_size[y]  #Addiere die Größe von y zur Größe von x
    self.parent_or_size[y] = x  #Der Anführer von y ist x
    return x

Finden Sie zuerst die Leiter x und y von a bzw. b. Wenn sie übereinstimmen, müssen Sie nichts tun, da a und b bereits zur selben Gruppe gehören (Zeile 5). Wenn nicht, führen Sie die y-Gruppe in die x-Gruppe ein. Führen Sie zu diesem Zeitpunkt in der 6. Zeile immer die kleine Gruppe in die große Gruppe ein. Gruppenmitglieder in y müssen die Informationen des Leiters aktualisieren, was den Rechenaufwand verringern kann.

2.4 Andere Methoden

In der ACL-DSU sind mehrere andere Methoden implementiert, daher werden wir sie auch implementieren.

same Durch Angabe von zwei Elementen gibt die gleiche Methode den booleschen Wert zurück, ob sie zur selben Gruppe gehören.

def same(self, a, b):
    assert 0 <= a < self._n
    assert 0 <= b < self._n
    return self.leader(a) == self.leader(b)

size Die Methodengröße gibt die Größe (Anzahl der Elemente) der Gruppe zurück, zu der das angegebene Element gehört.

def size(self, a):
    assert 0 <= a < self._n
    return -self.parent_or_size[self.leader(a)]

groups Die Methodengruppen geben eine Liste aller zusammen gruppierten Elemente zurück.

def groups(self):
    leader_buf = [self.leader(i) for i in range(self._n)]
    result = [[] for _ in range(self._n)]
    for i in range(self._n): result[leader_buf[i]].append(i)
    return [r for r in result if r != []]

2.5. Zusammenfassung

dsu.py

class DSU:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n
    
    def merge(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), self.leader(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    
    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]
    
    def groups(self):
        leader_buf = [self.leader(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[leader_buf[i]].append(i)
        return [r for r in result if r != []]

3. Anwendungsbeispiel

n = 8  #Gesamtzahl der Elemente
d = DSU(n)
d.merge(0, 1)
d.merge(1, 3)
d.merge(0, 4)
d.merge(5, 6)
d.merge(3, 7)
print(d.groups())  # [[0, 1, 3, 4, 7], [2], [5, 6]]
print(d.leader(3))  # 0
print(d.same(1, 7))  # True
print(d.same(0, 5))  # False
print(d.size(6))  # 2

4. Problembeispiel

AtCoder Library Practice Contest A "Disjoint Set Union" AtCoder Typical Contest 001 B "Union Find"

5. Schlussfolgerung

Von der Aufklärung des DSU-Mechanismus bis zur Implementierung in Python. Darüber hinaus wurde festgestellt, dass verschiedene Maßnahmen zur Umsetzung ergriffen wurden. Ich war besonders beeindruckt von der Idee, die notwendigen Informationen in einem einzigen Array auszudrücken.

Bitte lassen Sie uns wissen, wenn Sie Fehler, Bugs oder Ratschläge haben.