[GO] Minimale Implementierung von Union Find in Python

Hallo! Es tut mir Leid.

Selbst wenn ich manchmal Probleme mit Union Find habe, benutze ich meistens die Bibliotheken anderer Leute, deshalb schreibe ich es als Rezension. Wenn Sie denken, es ist wie eine vergessliche persönliche Notiz

Wichtiges Beispiel AtCoder Typical Contest 001 B --Union Find https://atcoder.jp/contests/atc001/tasks/unionfind_a

Es ist ein reines Problem von Union Find. Es gibt auch eine Kommentarfolie, daher werde ich sie entsprechend verstehen.

https://www.slideshare.net/chokudai/union-find-49066733 Union find (Elementarsatzdatenstruktur) von AtCoder Inc.

Union Find-Funktionen

1. Union
2. Ob es zu einer Gruppe gehört (Suchen)

Nur diese beiden. Das konkrete Bild der Gruppenbildung sieht so aus ↓ Es verbindet die durch Eingabe gegebenen Personen und behandelt sie als Baum.

Eine Gruppe erstellen

Gehörst du zu einer Gruppe?

Ob sie zu einer Gruppe gehören oder nicht, hängt davon ab, ob sie denselben Elternteil haben oder nicht.

Beschleunigung von Tipp 1: Pfadkomprimierung

Wenn es vertikal lang wird, dauert es jedes Mal einige Zeit, bis ein Elternteil gefunden ist. Diesmal ist es jedoch wichtig, zu welcher Gruppe Sie gehören. Daher ist es nicht so wichtig, wer mit wem verbunden ist. Sie können also beschleunigen, indem Sie sich bei jeder Suche direkt mit dem Elternteil verbinden.

Tipp 2 beschleunigen: Rang

Wenn Sie die Höhe des Baums beibehalten und den unteren mit dem höheren verbinden, wird die Berechnung der Pfadkomprimierung reduziert und beschleunigt

Implementierung (kein Rang)

Zunächst werden die Eltern jedes Elements von par (kurz für Eltern) verwaltet. Anfangs gehört jedes Element keiner Gruppe an, sodass Sie selbst zum übergeordneten Element werden. Wenn die Anzahl der Elemente N ist

par = [i for i in range(N+1)]

Es wird sein.

Nehmen wir als nächstes an, dass die Funktion, die das übergeordnete Element findet, find ist und die Funktion, die prüft, ob sich die Elemente x und y in derselben Gruppe befinden, identisch ist.

find

Wenn Sie der Elternteil sind, geben Sie Ihre Nummer zurück und suchen Sie in anderen Fällen den Elternteil erneut, um den Elternteil zu finden und die Verbindung wiederherzustellen (Routenkomprimierung).

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #Pfadkomprimierung
        return par[x]

same

Wir überprüfen die Eltern des anderen, um festzustellen, ob sie zur selben Gruppe gehören.

def same(x,y):
    return find(x) == find(y)

unite

Überprüfen Sie jeden Elternteil und vereinheitlichen Sie die Eltern nur, wenn sie unterschiedlich sind.

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y

Fassen Sie das Obige zusammen und lösen Sie dieses Beispiel

N,Q = map(int,input().split())
par = [i for i in range(N+1)]
def find(x):
    if par[x] == x:
        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
    par[x] = y
for i in range(Q):
    p,a,b = map(int,input().split())
    if p == 0:
        unite(a,b)
    else:
        if same(a,b):
            print('Yes')
        else:
            print('No')

https://atcoder.jp/contests/atc001/submissions/10365710

Muster zum Implementieren des Ranges

Bei der Implementierung des Ranges muss die Höhe jedes Scheitelpunkts verwaltet werden

N,Q = map(int,input().split())
par = [i for i in range(N+1)]
rank = [0]*(N+1)
def find(x):
    if par[x] == x:
        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
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x]==rank[y]:rank[x]+=1
        
for i in range(Q):
    p,a,b = map(int,input().split())
    if p == 0:
        unite(a,b)
    else:
        if same(a,b):
            print('Yes')
        else:
            print('No')

Schließlich

Das ist die Mindestimplementierung in Python. Wenn Sie etwas falsch finden, lassen Sie es uns bitte wissen!

Die Seite, auf die ich verweisen durfte

https://atcoder.jp/contests/atc001/tasks/unionfind_a

https://www.slideshare.net/chokudai/union-find-49066733