est. En d'autres termes, au moment de l'initialisation, tous les éléments appartiennent au "groupe de taille 1 avec vous comme leader (groupe avec vos propres éléments)".

2.2. Find L'opération Find est implémentée en ACL sous le nom leader. En spécifiant un élément, cette méthode renvoie le leader du groupe auquel appartient l'élément.

def leader(self, a):
    assert 0 <= a < self._n
    if self.parent_or_size[a] < 0: return a  #Leader si négatif
    self.parent_or_size[a] = self.leader(self.parent_or_size[a])
    return self.parent_or_size[a]

Premièrement, si parent_or_size [a] est négatif sur la troisième ligne, a est le leader et retourne tel quel. Sinon parent_or_size [a] est le lecteur ** (provisoire) ** de a. C'est parce qu'un leader n'est plus un leader s'il y a une intégration de groupe. Par conséquent, nous recherchons récursivement un ** vrai ** lecteur à partir de ce lecteur (provisoire). Les informations du lecteur sont mises à jour en remplaçant le côté droit dans la 4ème ligne sans la renvoyer directement. On peut dire qu'il est transformé en mémo. Cela raccourcira les recherches suivantes et suivantes.

2.3. Union L'opération Union est implémentée en ACL sous le nom de fusion. Cette méthode intègre les groupes auxquels ils appartiennent en spécifiant deux éléments.

def merge(self, a, b):
    assert 0 <= a < self._n
    assert 0 <= b < self._n
    x, y = self.leader(a), self.leader(b)
    if x == y: return x
    if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
    self.parent_or_size[x] += self.parent_or_size[y]  #Ajouter la taille de y à la taille de x
    self.parent_or_size[y] = x  #Le leader de y est x
    return x

Tout d'abord, trouvez les leaders x et y de a et b, respectivement. S'ils correspondent, vous n'avez rien à faire car a et b appartiennent déjà au même groupe (ligne 5). Sinon, fusionnez le groupe y dans le groupe x. A ce moment, en faisant la 6ème ligne, intégrez toujours le petit groupe dans le grand groupe. Les membres du groupe doivent mettre à jour les informations du leader, ce qui peut réduire la quantité de calcul.

2.4. Autres méthodes

Il existe plusieurs autres méthodes implémentées dans l'ACL DSU, nous allons donc les implémenter également.

same En spécifiant deux éléments, la méthode same renvoie la valeur booléenne indiquant s'ils appartiennent au même groupe.

def same(self, a, b):
    assert 0 <= a < self._n
    assert 0 <= b < self._n
    return self.leader(a) == self.leader(b)

size La méthode size renvoie la taille (nombre d'éléments) du groupe auquel appartient l'élément spécifié.

def size(self, a):
    assert 0 <= a < self._n
    return -self.parent_or_size[self.leader(a)]

groups La méthode groups renvoie une liste de tous les éléments regroupés.

def groups(self):
    leader_buf = [self.leader(i) for i in range(self._n)]
    result = [[] for _ in range(self._n)]
    for i in range(self._n): result[leader_buf[i]].append(i)
    return [r for r in result if r != []]

2.5. Résumé

dsu.py

class DSU:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n
    
    def merge(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), self.leader(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    
    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]
    
    def groups(self):
        leader_buf = [self.leader(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[leader_buf[i]].append(i)
        return [r for r in result if r != []]

3. Exemple d'utilisation

n = 8  #Nombre total d'éléments
d = DSU(n)
d.merge(0, 1)
d.merge(1, 3)
d.merge(0, 4)
d.merge(5, 6)
d.merge(3, 7)
print(d.groups())  # [[0, 1, 3, 4, 7], [2], [5, 6]]
print(d.leader(3))  # 0
print(d.same(1, 7))  # True
print(d.same(0, 5))  # False
print(d.size(6))  # 2

4. Exemple de problème

AtCoder Library Practice Contest A "Disjoint Set Union" AtCoder Typical Contest 001 B "Union Find"

5. Conclusion

De l'élucidation du mécanisme de DSU à l'implémentation en Python. En outre, il a été constaté que diverses mesures avaient été prises en termes de mise en œuvre. J'ai été particulièrement impressionné par l'idée d'exprimer les informations nécessaires dans un seul tableau.

Veuillez nous faire savoir si vous avez des erreurs, des bugs ou des conseils.