[PYTHON] Union Find sur networkX

Ceci est une introduction à la façon d'implémenter union find, qui est fréquemment utilisé dans atcoder, dans networkX au lieu d'implémenter votre propre bibliothèque. Quand je faisais des recherches sur networkX, j'ai trouvé unionfind, mais je n'ai pas trouvé d'article japonais sur unionfind dans networkX, je vais donc le présenter.

Le code ci-dessous est exécuté et AC avec la version python actuelle de atcoder. Python: 3.8.2 NetworkX: 2.4

modèle

networkxuf.py

from networkx.utils import UnionFind
uf = UnionFind()
uf.union(1, 2)  #Union 1 et 2
uf.union('atcoder', (3, 'chokudai')) # 'atcoder'Quand(3,'chokudai')syndicat
uf.union(2, 3, 4)
print(uf[2] == uf[(3, 'chokudai')])  #2 et(3,'chokudai')Est le même groupe(uf[a]Renvoie la racine d'un)
# False
print(uf['atcoder'] == uf[(3, 'chokudai')])
# True
print(uf.weights[uf[5]])  #Renvoie la taille de l'ensemble auquel appartient 5
# 1
print(uf.weights[uf[4]])
# 4
for group in uf.to_sets():  #Renvoie une liste de tous les groupes
    print(group)
"""
{1, 2, 3, 4}
{'atcoder', (3, 'chokudai')}
{5}
"""
for item in uf:
    print(item)
"""
1
2
atcoder
(3, 'chokudai')
3
4
5
"""

Comment utiliser

from networkx.utils import UnionFind uf = UnionFind() Importez unionfind pour créer une instance. Une fonctionnalité qui diffère de la méthode auto-implémentée que vous voyez souvent est que vous ne spécifiez pas le nombre d'éléments lors de la création d'une instance. Lors du référencement d'un élément avec la méthode décrite plus loin, il sera automatiquement généré s'il n'y a pas d'élément.

uf.union(1, 2) uf.union('atcoder', (3, 'chokudai')) uf.union(2, 3, 4) Une méthode pour combiner des éléments. Une fonctionnalité qui est différente de l'auto-implémentation que vous voyez souvent est que vous pouvez créer n'importe quel élément hachable. Cela peut être un élément, une chaîne ou un taple. Vous pouvez également combiner trois éléments ou plus ensemble. Je peux le faire.

print(uf[2] == uf[(3, 'chokudai')]) print(uf['atcoder'] == uf[(3, 'chokudai')]) Je n'ai pas trouvé de méthode pour déterminer si les éléments sont dans le même groupe, alors écrivez plutôt: Puisque ʻuf [x] `retourne la racine de x, il est jugé si les racines sont identiques.

print(uf.weights[uf[5]]) print(uf.weights[uf[4]]) Vous pouvez obtenir la taille du groupe avec uf.weights [root].

for group in uf.to_sets(): print(group) for item in uf: print(item) ʻUf.to_sets () retourne des itérateurs pour chaque groupe. Renvoie l'itérateur de l'élément individuel avec ʻuf.

point important

Contrairement à la méthode auto-implémentée que vous voyez souvent, si un élément n'est pas référencé dans l'union ou dans toute autre méthode, l'élément ne sera pas ajouté. Donc, si vous voulez obtenir le nombre de groupes comprenant des éléments non référencés avec ʻuf.to_sets () ʻetc., Vous devez faire référence à tous les éléments comme` _ = uf [x] 'etc. à l'avance.

Exemple pratique

AtCoder Library Practice Contest A Disjoint Set Union　 https://atcoder.jp/contests/practice2/submissions/16927433

ACL Beginner Contest C Connect Cities (Utilisation dans la production du concours)

https://atcoder.jp/contests/abl/submissions/17038431

AtCoder Beginner Contest 177 D Friends https://atcoder.jp/contests/abc177/submissions/16927545

Concours de programmation Acing 2019 C Chemin alterné

https://atcoder.jp/contests/aising2019/submissions/17055243 Vous pouvez également effectuer cette opération car vous pouvez trouver des unions autres que des valeurs numériques.

AtCoder Beginner Contest 040 D À propos des mesures contre le vieillissement des routes (à peine!)

https://atcoder.jp/contests/abc040/submissions/17055355

CODE FESTIVAL 2016 Final C Interpretation https://atcoder.jp/contests/cf16-final-open/submissions/17078026 Vous pouvez en trouver 3 ou plus en même temps, vous pouvez donc écrire de manière concise comme ceci

AtCoder Regular Contest 027 B Comme c'est un nombre important, je l'ai écrit Z fois.

https://atcoder.jp/contests/arc027/submissions/17078209 Les chaînes de caractères peuvent également être une recherche d'union, donc elles peuvent être implémentées comme ceci.

Quelle est la vitesse?

Bien sûr, il est lent car il s'agit de networkX. Vous trouverez ci-dessous une comparaison de vitesse entre l'exemple de pratique ci-dessus et la propre implémentation de unionfind.

De cette façon, il est deux fois plus lent que l'auto-implémentation et environ 200 ms plus lent. Cependant, s'il s'agit d'un problème simple et mineur, cela suffira. Pour les problèmes simples, non seulement le temps d'exécution mais aussi le temps d'implémentation sont importants, donc networkX, qui peut être facilement implémenté sans chercher et copier la bibliothèque, sera un bon choix.

Résumé

networkX a des fonctionnalités que nous ne connaissons pas encore. Après tout, l'abondance des bibliothèques est la force de python. (Autre que multiset ...)