In [1]:

    

from union_find import UnionFind, UnionFindLabel


    

In [2]:

    

uf = UnionFind(6)
print(uf.parents)


    

    




[-1, -1, -1, -1, -1, -1]

In [3]:

    

print(uf)


    

    




0: [0]
1: [1]
2: [2]
3: [3]
4: [4]
5: [5]

In [4]:

    

uf.union(0, 2)
print(uf.parents)


    

    




[-2, -1, 0, -1, -1, -1]

In [5]:

    

print(uf)


    

    




0: [0, 2]
1: [1]
3: [3]
4: [4]
5: [5]

In [6]:

    

uf.union(1, 3)
print(uf.parents)
uf.union(4, 5)
print(uf.parents)
uf.union(1, 4)
print(uf.parents)


    

    




[-2, -2, 0, 1, -1, -1]
[-2, -2, 0, 1, -2, 4]
[-2, -4, 0, 1, 1, 4]

In [7]:

    

print(uf)


    

    




0: [0, 2]
1: [1, 3, 4, 5]

In [8]:

    

print(uf.parents)


    

    




[-2, -4, 0, 1, 1, 1]

In [9]:

    

print(uf.find(0))


    

    




0

In [10]:

    

print(uf.find(5))


    

    




1

In [11]:

    

print(uf.size(0))


    

    




2

In [12]:

    

print(uf.size(5))


    

    




4

In [13]:

    

print(uf.same(0, 2))


    

    




True

In [14]:

    

print(uf.same(0, 5))


    

    




False

In [15]:

    

print(uf.members(0))


    

    




[0, 2]

In [16]:

    

print(uf.members(5))


    

    




[1, 3, 4, 5]

In [17]:

    

print(uf.roots())


    

    




[0, 1]

In [18]:

    

print(uf.group_count())


    

    




2

In [19]:

    

print(uf.all_group_members())


    

    




{0: [0, 2], 1: [1, 3, 4, 5]}

In [20]:

    

print(list(uf.all_group_members().values()))


    

    




[[0, 2], [1, 3, 4, 5]]

In [21]:

    

l = ['A', 'B', 'C', 'D', 'E']


    

In [22]:

    

d = {x: i for i, x in enumerate(l)}
print(d)


    

    




{'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4}

In [23]:

    

d_inv = {i: x for i, x in enumerate(l)}
print(d_inv)


    

    




{0: 'A', 1: 'B', 2: 'C', 3: 'D', 4: 'E'}

In [24]:

    

uf_s = UnionFind(len(l))
print(uf_s)


    

    




0: [0]
1: [1]
2: [2]
3: [3]
4: [4]

In [25]:

    

uf_s.union(d['A'], d['D'])
uf_s.union(d['D'], d['C'])
uf_s.union(d['E'], d['B'])
print(uf_s)


    

    




0: [0, 2, 3]
4: [1, 4]

In [26]:

    

print(d_inv[uf_s.find(d['D'])])


    

    




A

In [27]:

    

print(uf_s.size(d['D']))


    

    




3

In [28]:

    

print(uf_s.same(d['A'], d['D']))


    

    




True

In [29]:

    

print([d_inv[i] for i in uf_s.members(d['D'])])


    

    




['A', 'C', 'D']

In [30]:

    

print([d_inv[i] for i in uf_s.roots()])


    

    




['A', 'E']

In [31]:

    

print(uf_s.group_count())


    

    




2

In [32]:

    

l = ['A', 'B', 'C', 'D', 'E']


    

In [33]:

    

ufl = UnionFindLabel(l)
print(ufl)


    

    




A: ['A']
B: ['B']
C: ['C']
D: ['D']
E: ['E']

In [34]:

    

ufl.union('A', 'D')
ufl.union('D', 'C')
ufl.union('E', 'B')
print(ufl)


    

    




A: ['A', 'C', 'D']
E: ['B', 'E']

In [35]:

    

print(ufl.find_label('D'))


    

    




A

In [36]:

    

print(ufl.size('D'))


    

    




3

In [37]:

    

print(ufl.same('A', 'D'))


    

    




True

In [38]:

    

print(ufl.members('D'))


    

    




['A', 'C', 'D']

In [39]:

    

print(ufl.roots())


    

    




['A', 'E']

In [40]:

    

print(ufl.group_count())


    

    




2

In [41]:

    

print(ufl.all_group_members())


    

    




{'A': ['A', 'C', 'D'], 'E': ['B', 'E']}

In [42]:

    

ufl_n = UnionFindLabel([1, 2, 3, 4, 5])
print(ufl_n)


    

    




1: [1]
2: [2]
3: [3]
4: [4]
5: [5]

In [43]:

    

ufl_n.union(1, 4)
ufl_n.union(4, 3)
ufl_n.union(5, 2)
print(ufl_n)


    

    




1: [1, 3, 4]
5: [2, 5]

In [44]:

    

ufl_n2 = UnionFind(6)
print(ufl_n2)


    

    




0: [0]
1: [1]
2: [2]
3: [3]
4: [4]
5: [5]

In [45]:

    

ufl_n2.union(1, 4)
ufl_n2.union(4, 3)
ufl_n2.union(5, 2)
print(ufl_n2)


    

    




0: [0]
1: [1, 3, 4]
5: [2, 5]

In [46]:

    

ufl_t = UnionFindLabel([(0, 0), (0, 1), (1, 0), (1,1)])
print(ufl_t)


    

    




(0, 0): [(0, 0)]
(0, 1): [(0, 1)]
(1, 0): [(1, 0)]
(1, 1): [(1, 1)]

In [47]:

    

ufl_t.union((0, 1), (1, 0))
ufl_t.union((0, 0), (1, 0))
print(ufl_t)


    

    




(0, 1): [(0, 0), (0, 1), (1, 0)]
(1, 1): [(1, 1)]

In [48]:

    

print(ufl_t.same((0, 1), (0, 0)))


    

    




True