[PYTHON] [Competition Pro Struggle] Implémentation de la recherche d'union

motivation

Je suis un programmeur faible, mais j'ai décidé de commencer une programmation compétitive afin de devenir un programmeur fort. Comme vous pouvez le voir lorsque vous l'essayez, vous vous en souvenez souvent. Je pense que je résous les mathématiques à l'examen, mais bien sûr, la capacité de réflexion est importante, mais pour obtenir la réponse en peu de temps lors de l'examen proprement dit, il est également important d'avoir beaucoup de retraits.

Par conséquent, nous implémenterons les principaux algorithmes et structures de données un par un.

Cette fois, c'est la première fois, nous allons implémenter une structure de données appelée Union Find.

Au fait, comme la motivation des pros de la compétition est de faire des affaires efficacement, j'utiliserai mon langage préféré Python au lieu du C ++ que tout le monde en compétition utilise plutôt que Po ** Hub. (J'ai vu dans un article que C ++ est 4 fois plus rapide, mais 4 fois est une erreur, n'est-ce pas?)

UnionFind La recherche d'union se produit lorsque N nœuds sont divisés en groupes

1. Connectez les groupes auxquels appartiennent deux nœuds a et b en un seul groupe.
2. Déterminez si deux nœuds a et b appartiennent au même groupe Une structure de données spécialisée pour la fonction.

Les deux peuvent être mis en œuvre avec le journal des montants de calcul de l'effraction (N).

algorithme

Toutes les images proviennent de Nice slide

la mise en oeuvre

Structure de données

Les programmeurs faibles ne savent pas comment conserver les données en premier, mais UnionFind est une ** structure arborescente qui ** se souvient de qui est le nœud parent. Donc, si vous souhaitez regrouper n nœuds, il vous suffit de ** une liste contenant les parents de chaque nœud **.

class UnionFind:
    def __init__(self, n):
        self.parents = list(range(n))
    ...

Au fait, puisque le nœud racine n'a pas de parent, ** le parent l'exprime comme son propre nœud = nœud racine. ** ** Au début, ce sont tous des nœuds racine car ils sont initialisés en tant que groupes séparés.

Jugement

    def is_united(self, x, y):
        return self._root(x) == self._root(y)

Comme vous pouvez le voir dans l'image citée de la jolie diapositive, il vous suffit de déterminer si les nœuds racine sont les mêmes, utilisez donc la méthode _root pour extraire les nœuds racine et comparez s'ils sont égaux. C'est très bien.

Lors de l'écriture de code, je pense qu'il est plus facile d'écrire rapidement l'ensemble de l'algorithme en pensant qu'il existe déjà une fonction terminée pour le sous-algorithme détaillé.

Si vous n'aviez pas cuisiné pendant 3 minutes et que vous disiez: «Aujourd'hui, j'ai une pomme de terre fumée qui a été préparée ici», je ne pourrais pas voir l'image complète du plat.

Joindre

    def union(self, x, y):
        self.parents[self._root(y)] = self._root(x)

C'est aussi exactement comme il a été écrit sur la jolie diapositive, et si vous voulez combiner le groupe de x et le groupe de y, il vous suffit d'attacher l'un des nœuds racine au nœud racine de l'autre.

Même si vous dites d'attacher, vous spécifiez simplement le parent du nœud que vous souhaitez attacher au nœud auquel vous attacher.

Obtenez le nœud racine

Le seul sous-algorithme que j'ai utilisé jusqu'à présent est _root, donc l'implémentation devrait être terminée.

    def _root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root = self._root(self.parents[x])
            return root

Pour renvoyer le nœud racine, il suffit de revenir au nœud parent jusqu'à ce qu'un nœud dans lequel le parent devient lui-même apparaisse. La structure de données arborescente UnionFind est simple car elle fait référence au parent de chaque nœud.

Cependant, il était écrit sur une grande diapositive que la quantité de calcul serait plus légère si la structure arborescente était aussi plate que possible en raison de la quantité de calcul.

Je vais donc ajouter un peu d'ingéniosité au code.

    def _root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root = self._root(self.parents[x])
            self.parents[x] = root  #Reconnectez-vous directement au nœud parent.
            return root

Ceci termine Union Find!

Essayez de bouger

uf = UnionFind(5)
uf.union(0, 3)
uf.union(1, 3)
print(uf.is_united(0, 1))  # True

La fin

Je recherche un compagnon qui travaillera dur en tant qu'ingénieur ensemble. Je serais très heureux si vous suivez LGTM, Follow et Twitter.