Implémentation minimale d'Union Find en Python

salut! Je suis désolé.

Même si j'ai parfois des problèmes avec Union Find, j'ai tendance à utiliser les bibliothèques d'autres personnes, je vais donc l'écrire comme une critique. Si vous pensez que c'est comme une note personnelle oublieuse

Exemple important Concours typique AtCoder 001 B - Union Find https://atcoder.jp/contests/atc001/tasks/unionfind_a

C’est un pur problème de Union Find. Il y a aussi une diapositive de commentaires, donc je vais la comprendre en conséquence.

https://www.slideshare.net/chokudai/union-find-49066733 Recherche d'union (structure de données d'ensemble élémentaire) d'AtCoder Inc

Fonctionnalités de Union Find

1. Union
2. S'il appartient à un groupe (Rechercher)

Seulement ces deux. L'image concrète de la création de groupe ressemble à ceci ↓ Il relie les personnes données par l'entrée et les traite comme un arbre.

Créer un groupe

Appartenez-vous à un groupe

L'appartenance ou non à un groupe est déterminée par le fait qu'ils aient ou non le même parent.

Accélérer le conseil 1: Compression de chemin

Si cela devient long verticalement, il faudra du temps pour trouver un parent à chaque fois. Cependant, cette fois, le groupe auquel vous appartenez est important, il n'est donc pas si important de savoir qui est connecté à qui, vous pouvez donc accélérer en vous connectant directement au parent chaque fois que vous le trouvez.

Accélérer Astuce2: Rang

En gardant la hauteur de l'arbre et en connectant le plus bas au plus haut, la quantité de calcul de compression de chemin est réduite et la vitesse est augmentée.

Mise en œuvre (pas de rang)

Premièrement, les parents de chaque élément sont gérés par par (abréviation de parents). Au départ, chaque élément n'appartient à aucun groupe, vous devenez donc vous-même le parent. Si le nombre d'éléments est N

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

Ce sera.

Ensuite, disons que la fonction qui trouve son parent est find, et la fonction qui vérifie si les éléments x et y sont dans le même groupe est la même

find

Si vous êtes le parent, renvoyez votre numéro, sinon retrouvez le parent pour retrouver le parent et vous reconnecter (route de compression).

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #Compression de chemin
        return par[x]

same

Nous vérifions les parents les uns des autres pour voir s'ils sont dans le même groupe.

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

unite

Vérifiez chaque parent et unifiez les parents uniquement s'ils sont différents.

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

Résumer ce qui précède et résoudre cet exemple

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]) #Compression de chemin
        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

Modèle pour implémenter le rang

Lors de la mise en œuvre du rang, il est nécessaire de gérer la hauteur de chaque sommet

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]) #Compression de chemin
        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')

finalement

C'est l'implémentation minimale en Python. Si vous trouvez quelque chose qui ne va pas, veuillez nous en informer!

Le site auquel j'ai pu me référer

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

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