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
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.
L'appartenance ou non à un groupe est déterminée par le fait qu'ils aient ou non le même parent.
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.
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.
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')
C'est l'implémentation minimale en Python. Si vous trouvez quelque chose qui ne va pas, veuillez nous en informer!
https://atcoder.jp/contests/atc001/tasks/unionfind_a
https://www.slideshare.net/chokudai/union-find-49066733
Recommended Posts