Obtenir la taille (nombre d'éléments) de Union Find en Python
Je suis désolé. Deuxième note pour moi
La dernière fois que j'ai écrit l'implémentation minimale d'Union-Find, UnionFind est maintenant sans égal! j'ai pensé
ABC157 D-Friend Suggestion
https://atcoder.jp/contests/abc157/tasks/abc157_d
Le problème d'AtCoder m'a rendu confus.
La cause est que nous n'avons pas pu implémenter la taille (nombre d'éléments). Réimplémentons.
Code d'implémentation
N,Q = map(int,input().split())
par = [-1]*(N+1)
def find(x):
if par[x] < 0:
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
else:
if par[x] > par[y]:
x,y = y,x
par[x] += par[y]
par[y] = x
def size(x):
return -par[find(x)]
Ceci est la version révisée.
Initialisation
par = [-1]*(N+1)
Il est à noter que toutes les valeurs initiales initiales sont mises à -1 et gérées.
Si vous êtes parent, vous êtes jugé selon que vous êtes négatif ou non.
Unir
def unite(x,y):
x = find(x)
y = find(y)
if x == y:
return 0
else:
if par[x] > par[y]:
x,y = y,x
par[x] += par[y]
par[y] = x
Est de prendre la somme négative des deux parents lors de l'adhésion.
Ce faisant, l'élément enfant de par contiendra le numéro du nœud parent.
La taille (nombre d'éléments) de l'arbre peut être considérée comme une valeur négative dans l'élément parent du par.
Exemple
Par exemple, dans cette image, ce sera [-5, 0, 0, 0, 0].
size
Maintenant, il est clair pourquoi la valeur de retour de la fonction de taille a un moins «ー»!
def size(x):
return -par[find(x)]
Résumé
J'ai été surpris au début qu'un moins apparaisse avant le retour même si je n'avais que la taille, mais c'était très facile à comprendre une fois que je l'ai compris.
Cette fois, Union Find devrait pouvoir correspondre!
Recommended Posts