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

Recommended Posts

Implémentation minimale d'Union Find en Python
[Python] Comment faire PCA avec Python
Je veux faire le test de Dunnett en Python
Implémentation RNN en python
Implémentation ValueObject en Python
La chose semblable à une recherche de liste en Python
Que faire pour obtenir une feuille de calcul Google en Python
Implémentation SVM en python
Comment faire un calcul de hachage avec Salt en Python
Pour faire l'équivalent de Ruby ObjectSpace._id2ref en Python
Je veux faire quelque chose avec Python à la fin
Trouver des erreurs en Python
Connectez-vous au site Web en Python
Trouvez l'ordre / la combinaison en Python
Parler avec Python [synthèse vocale]
Implémentation de réseau neuronal en python
Comment développer en Python
Implémentation du tri rapide en Python
Trouvons le rapport de circonférence avec Python
Publier sur Slack en Python
Que faire lorsque ʻarguments [0] .scrollIntoView (); `échoue dans python sélénium
Je veux faire quelque chose comme sort uniq en Python
Que faire lorsque "SSL: CERTIFICATE_VERIFY_FAILED _ssl.c: 1056" apparaît en Python
Convertir Markdown en PDF en Python
Algorithme de tri et implémentation en Python
Comment collecter des images en Python
Implémentation de l'estimation des paramètres HMM en python
Implémentation de distribution normale mixte en python
Comment utiliser SQLite en Python
Dans la commande python, python pointe vers python3.8
Implémentation du jeu de vie en Python
Pour faire une récursion avec Python2
Essayez de calculer Trace en Python
Que faire avec la sortie de PYTHON?
Comment utiliser Mysql avec python
Comment envelopper C en Python
Comment utiliser ChemSpider en Python
6 façons d'enchaîner des objets en Python
Comment utiliser PubChem avec Python
Implémentation du tri original en Python
les débutants en python ont essayé de le découvrir
Comment gérer le japonais avec Python
Une alternative à `pause` en Python
Voulez-vous attendre un usage général avec Python Selenium?
Que faire si vous obtenez moins zéro en Python
Je voulais faire quelque chose comme la pipe d'Elixir en Python
Que faire lorsque ModuleNotFoundError: Aucun module nommé'XXX 'ne se produit en Python
Que faire lorsque le type de valeur est ambigu en Python?
J'ai essayé d'implémenter PLSA en Python
[Introduction à Python] Comment utiliser la classe en Python?
Essayez de vous connecter à qiita avec Python
Que faire s'il y a un décimal dans python json .dumps
Installez Pyaudio pour lire des vagues en python
J'ai essayé d'implémenter la permutation en Python
Méthode pour créer un environnement Python dans Xcode 6
Que faire si PDO n'est pas trouvé dans Laravel ou CakePHP
Faites une visite Euler non récursive en Python
Comment définir dynamiquement des variables en Python
Trouver des fichiers comme Linux Find en Python
Module d'implémentation de file d'attente et Python "deque"