[PYTHON] Union Find on networkX

This is an introduction of how to implement union find, which is frequently used in atcoder, with networkX instead of implementing your own library. When I was researching networkX, I found unionfind, but I couldn't find a Japanese article about unionfind in networkX, so I will introduce it.

The code below is executed and AC with the current python version of atcoder. Python: 3.8.2 NetworkX: 2.4

template

networkxuf.py

from networkx.utils import UnionFind
uf = UnionFind()
uf.union(1, 2)  #Union 1 and 2
uf.union('atcoder', (3, 'chokudai')) # 'atcoder'When(3,'chokudai')Union
uf.union(2, 3, 4)
print(uf[2] == uf[(3, 'chokudai')])  #2 and(3,'chokudai')Is the same group(uf[a]Returns the root of a)
# False
print(uf['atcoder'] == uf[(3, 'chokudai')])
# True
print(uf.weights[uf[5]])  #Returns the size of the set to which 5 belongs
# 1
print(uf.weights[uf[4]])
# 4
for group in uf.to_sets():  #Returns a list of all groups
    print(group)
"""
{1, 2, 3, 4}
{'atcoder', (3, 'chokudai')}
{5}
"""
for item in uf:
    print(item)
"""
1
2
atcoder
(3, 'chokudai')
3
4
5
"""

How to use

from networkx.utils import UnionFind uf = UnionFind() Import unionfind to create an instance. The feature that is different from the self-implemented method that you often see is that you do not specify the number of elements when creating an instance. When referencing an element with the method described below, it will be automatically generated if there is no element.

uf.union(1, 2) uf.union('atcoder', (3, 'chokudai')) uf.union(2, 3, 4) A method that combines elements. The feature that is different from the self-implementation that you often see is that you can make any hashable element. It can be an element, either a string or a tuple. You can also combine three or more elements together. I can do it.

print(uf[2] == uf[(3, 'chokudai')]) print(uf['atcoder'] == uf[(3, 'chokudai')]) I couldn't find a method to determine if the elements are in the same group, so instead write: Since ʻuf [x] `returns the root of x, it is judged whether the roots are the same.

print(uf.weights[uf[5]]) print(uf.weights[uf[4]]) You can get the size of the group with uf.weights [root].

for group in uf.to_sets(): print(group) for item in uf: print(item) ʻUf.to_sets () returns the iterators set for each group. Returns an iterator for individual elements with ʻuf.

important point

Unlike the self-implemented method that you often see, if an element is not referenced in a union or other method, the element will not be added. So, if you want to get the number of groups including unreferenced elements with ʻuf.to_sets () etc., you have to refer all the elements as _ = uf [x]' etc. in advance.

Practical example

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

ACL Beginner Contest C Connect Cities (Use in Contest Production)

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

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

Acing Programming Contest 2019 C Alternating Path

https://atcoder.jp/contests/aising2019/submissions/17055243 You can also do this because you can union find other than numerical values.

AtCoder Beginner Contest 040 D Road aging countermeasures (barely!)

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

CODE FESTIVAL 2016 Final C Interpretation https://atcoder.jp/contests/cf16-final-open/submissions/17078026 You can union find 3 or more at the same time, so you can write concisely like this

AtCoder Regular Contest 027 B Since it is an important number, I wrote it Z times.

https://atcoder.jp/contests/arc027/submissions/17078209 Strings can also be union find, so it can be implemented like this.

What is the speed?

Of course it is slow because it is networkX. Below is a speed comparison between the above practice example and unionfind's own implementation.

In this way, it is twice as slow as the self-implementation and about 200ms slower. But if it's a simple, minor problem, it's good enough. For simple problems, not only execution time but also implementation time is important, so networkX, which can be easily implemented without searching for and copying the library, will be a good choice.

Summary

networkX has some features that we don't know yet. After all the abundance of libraries is the strength of python. (Other than multiset ...)