Ermitteln Sie die Größe (Anzahl der Elemente) von Union Find in Python
Es tut mir Leid. Zweite Anmerkung für mich
Das letzte Mal habe ich die Mindestimplementierung von Union-Find geschrieben und jetzt ist UnionFind unübertroffen! ich dachte
ABC157 D-Friend Suggestion
https://atcoder.jp/contests/abc157/tasks/abc157_d
Das Problem von AtCoder hat mich verwirrt.
Die Ursache ist, dass die Implementierung zum Abrufen der Größe (Anzahl der Elemente) nicht durchgeführt wurde. Lassen Sie uns neu implementieren.
Implementierungscode
N,Q = map(int,input().split())
par = [-1]*(N+1)
def find(x):
if par[x] < 0:
return x
else:
par[x] = find(par[x]) #Pfadkomprimierung
return par[x]
def same(x,y):
return find(x) == find(y)
def unite(x,y):
x = find(x)
y = find(y)
if x == y:
return 0
else:
if par[x] > par[y]:
x,y = y,x
par[x] += par[y]
par[y] = x
def size(x):
return -par[find(x)]
Dies ist die überarbeitete Version.
Initialisieren
par = [-1]*(N+1)
Es ist zu beachten, dass alle anfänglichen Anfangswerte auf -1 gesetzt und verwaltet werden.
Wenn Sie ein Elternteil sind, werden Sie danach beurteilt, ob Sie negativ sind oder nicht.
Vereinen
def unite(x,y):
x = find(x)
y = find(y)
if x == y:
return 0
else:
if par[x] > par[y]:
x,y = y,x
par[x] += par[y]
par[y] = x
Ist die negative Summe beider Elternteile beim Beitritt zu nehmen.
Auf diese Weise enthält das untergeordnete Element von par die Nummer des übergeordneten Knotens.
Die Größe (Anzahl der Elemente) des Baums kann im übergeordneten Element von par als negativer Wert angegeben werden.
Beispiel
In diesem Bild ist es beispielsweise [-5, 0, 0, 0, 0].
size
Jetzt ist klar, warum der Rückgabewert der Größenfunktion ein Minus-has hat!
def size(x):
return -par[find(x)]
Zusammenfassung
Ich war zuerst überrascht, dass vor der Rückkehr ein Minus erschien, obwohl ich nur die Größe bekam, aber es war sehr leicht zu verstehen, sobald ich es verstanden hatte.
Diesmal sollte Union Find mithalten können!
Recommended Posts