[PYTHON] Union Find auf networkX

Dies ist eine Einführung in die Implementierung von Union Find, die häufig in atcoder verwendet wird, in networkX, anstatt Ihre eigene Bibliothek zu implementieren. Als ich über networkX recherchierte, fand ich unionfind, aber ich konnte keinen japanischen Artikel über unionfind in networkX finden, daher werde ich ihn vorstellen.

Der folgende Code wird ausgeführt und AC mit der aktuellen Python-Version von atcoder. Python: 3.8.2 NetworkX: 2.4

Vorlage

networkxuf.py

from networkx.utils import UnionFind
uf = UnionFind()
uf.union(1, 2)  #Union 1 und 2
uf.union('atcoder', (3, 'chokudai')) # 'atcoder'Wann(3,'chokudai')Union
uf.union(2, 3, 4)
print(uf[2] == uf[(3, 'chokudai')])  #2 und(3,'chokudai')Ist die gleiche Gruppe(uf[a]Gibt die Wurzel von a zurück)
# False
print(uf['atcoder'] == uf[(3, 'chokudai')])
# True
print(uf.weights[uf[5]])  #Gibt die Größe des Satzes zurück, zu dem 5 gehört
# 1
print(uf.weights[uf[4]])
# 4
for group in uf.to_sets():  #Gibt eine Liste aller Gruppen zurück
    print(group)
"""
{1, 2, 3, 4}
{'atcoder', (3, 'chokudai')}
{5}
"""
for item in uf:
    print(item)
"""
1
2
atcoder
(3, 'chokudai')
3
4
5
"""

Wie benutzt man

from networkx.utils import UnionFind uf = UnionFind() Importieren Sie unionfind, um eine Instanz zu erstellen. Eine Funktion, die sich von der häufig implementierten selbst implementierten Methode unterscheidet, besteht darin, dass Sie beim Erstellen einer Instanz nicht die Anzahl der Elemente angeben. Wenn Sie mit der später beschriebenen Methode auf ein Element verweisen, wird es automatisch generiert, wenn kein Element vorhanden ist.

uf.union(1, 2) uf.union('atcoder', (3, 'chokudai')) uf.union(2, 3, 4) Eine Methode zum Kombinieren von Elementen. Eine Funktion, die sich von der Selbstimplementierung unterscheidet, die Sie häufig sehen, ist, dass Sie jedes Hash-Element erstellen können. Es kann ein Element sein, entweder eine Schnur oder ein Taple. Sie können auch drei oder mehr Elemente miteinander kombinieren. Ich kann es schaffen

print(uf[2] == uf[(3, 'chokudai')]) print(uf['atcoder'] == uf[(3, 'chokudai')]) Ich konnte keine Methode finden, um festzustellen, ob sich die Elemente in derselben Gruppe befinden. Schreiben Sie stattdessen: Da uf [x] die Wurzel von x zurückgibt, wird beurteilt, ob die Wurzeln gleich sind.

print(uf.weights[uf[5]]) print(uf.weights[uf[4]]) Sie können die Größe der Gruppe mit uf.weights [root] ermitteln.

for group in uf.to_sets(): print(group) for item in uf: print(item) uf.to_sets () gibt die für jede Gruppe festgelegten Iteratoren zurück. uf gibt den Iterator des einzelnen Elements zurück.

wichtiger Punkt

Im Gegensatz zu der häufig implementierten selbst implementierten Methode wird das Element nicht hinzugefügt, wenn in einer Union oder einer anderen Methode nicht auf ein Element verwiesen wird. Wenn Sie also die Anzahl der Gruppen einschließlich nicht referenzierter Elemente mit "uf.to_sets ()" usw. ermitteln möchten, müssen Sie alle Elemente im Voraus als "_ = uf [x]" bezeichnen.

Praktisches Beispiel

AtCoder Library Practice Contest A Disjoint Set Union　 https://atcoder.jp/contests/practice2/submissions/16927433

ACL-Anfängerwettbewerb C Connect Cities (Verwendung in der Wettbewerbsproduktion)

https://atcoder.jp/contests/abl/submissions/17038431

AtCoder Beginner Contest 177 D Friends https://atcoder.jp/contests/abc177/submissions/16927545

Acing Programmierwettbewerb 2019 C Alternierender Pfad

https://atcoder.jp/contests/aising2019/submissions/17055243 Sie können dies auch tun, weil Sie andere als numerische Werte vereinen können.

AtCoder Anfängerwettbewerb 040 D Über Maßnahmen gegen alternde Straßen (kaum!)

https://atcoder.jp/contests/abc040/submissions/17055355

CODE FESTIVAL 2016 Final C Interpretation https://atcoder.jp/contests/cf16-final-open/submissions/17078026 Sie können 3 oder mehr gleichzeitig finden, so dass Sie so prägnant schreiben können

AtCoder Regular Contest 027 B Da es sich um eine wichtige Zahl handelt, habe ich sie Z-mal geschrieben.

https://atcoder.jp/contests/arc027/submissions/17078209 Zeichenketten können auch Union Find sein, so dass sie wie folgt implementiert werden können.

Was ist die Geschwindigkeit?

Natürlich ist es langsam, weil es networkX ist. Nachfolgend finden Sie einen Geschwindigkeitsvergleich zwischen dem obigen Übungsbeispiel und der eigenen Implementierung von unionfind.

Auf diese Weise ist es doppelt so langsam wie die Selbstimplementierung und etwa 200 ms langsamer. Wenn es sich jedoch um ein einfaches und geringfügiges Problem handelt, reicht es aus. Bei einfachen Problemen ist nicht nur die Ausführungszeit, sondern auch die Implementierungszeit wichtig. Daher ist networkX, das einfach implementiert werden kann, ohne die Bibliothek zu suchen und zu kopieren, eine gute Wahl.

Zusammenfassung

networkX hat einige Funktionen, die wir noch nicht kennen. Immerhin ist die Fülle an Bibliotheken die Stärke von Python. (Außer Multiset ...)