[Python] UnionFind ABC177D

ABC177D

Il existe différentes implémentations d'UnionFind, mais dans cette question, il est très facile de résoudre l'implémentation qui contient le nombre de nœuds dans le tableau des parents. Le nombre de nœuds est tenu comme suit.

-Lorsqu'il s'agit d'un enfant, il stocke le numéro de nœud parent. Lorsqu'il s'agit d'une racine, il stocke le nombre de nœuds sous forme de nombre négatif. -Lorsque le nombre est négatif, c'est la racine, et sa valeur absolue représente le nombre de nœuds dans l'arborescence.

`Exemple de code`


import sys

#Définition de classe UnionFindTree
class UnionFind():
    #Constructeur de classe
    #soi est l'instance elle-même
    def __init__(self, n):
        #Noeud parent-Initialiser à 1
        self.parents = [-1] * n

    #Trouvez la racine
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    #Fusionner les arbres x et y
    def union(self, x, y):
        #À la recherche de racines
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

#Création d'une instance Union Find
uf = UnionFind(N)
for a, b in info:
    #Ajustez l'index, un,Rejoindre l'arbre b
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)