Skip to content

Instantly share code, notes, and snippets.

@cceasy

cceasy/disjoint_set.py

Last active August 31, 2020 08:50
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save cceasy/b9a96f8c6f61760eb1c5f965202f9f28 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save cceasy/b9a96f8c6f61760eb1c5f965202f9f28 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. cceasy revised this gist Aug 31, 2020. 2 changed files with 9 additions and 5 deletions.
    6 changes: 3 additions & 3 deletions disjoint_set.py
    View file
    Original file line number Diff line number Diff line change
    @@ -15,8 +15,8 @@ def tree_num(self):
    return num

    def find(self, i):
    while (self.index[i] != i):
    i = self.index[i]
    if (self.index[i] != i):
    self.index[i] = self.find(self.index[i]) # optimize path
    return self.index[i]

    def union(self, i, j):
    @@ -32,4 +32,4 @@ def union(self, i, j):
    self.depth[index_j] += 1

    def __str__(self):
    return 'index: {}\ndepth: {}'.format(self.index, self.depth)
    return 'items: {}\nindex: {}\ndepth: {}'.format(list(range(len(self.index))), self.index, self.depth)
    8 changes: 6 additions & 2 deletions test.py
    View file
    Original file line number Diff line number Diff line change
    @@ -5,7 +5,11 @@
    for pair in links:
    js.union(pair[0], pair[1])
    print(js.tree_num())
    print(js)

    # 6
    # CPU times: user 0 ns, sys: 0 ns, total: 0 ns
    # Wall time: 127 µs
    # items: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    # index: [0, 2, 5, 2, 4, 5, 5, 7, 8, 9]
    # depth: [0, 0, 1, 0, 0, 1, 0, 0, 0, 0]
    # CPU times: user 4 ms, sys: 0 ns, total: 4 ms
    # Wall time: 143 µs
  2. cceasy revised this gist Aug 31, 2020. 1 changed file with 5 additions and 1 deletion.
    6 changes: 5 additions & 1 deletion test.py
    View file
    Original file line number Diff line number Diff line change
    @@ -4,4 +4,8 @@
    links = [[1,2], [2,3], [3,5], [5, 6]]
    for pair in links:
    js.union(pair[0], pair[1])
    print(js.tree_num())
    print(js.tree_num())

    # 6
    # CPU times: user 0 ns, sys: 0 ns, total: 0 ns
    # Wall time: 127 µs
  3. cceasy created this gist Aug 31, 2020.
    35 changes: 35 additions & 0 deletions disjoint_set.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,35 @@
    class DisjointSet(object):

    index = list()
    depth = list()

    def __init__(self, n):
    self.index = list(range(n))
    self.depth = [0] * n

    def tree_num(self):
    num = 0
    for i in range(len(self.index)):
    if self.index[i] == i:
    num += 1
    return num

    def find(self, i):
    while (self.index[i] != i):
    i = self.index[i]
    return self.index[i]

    def union(self, i, j):
    index_i = self.find(i)
    index_j = self.find(j)
    if index_i != index_j:
    if self.depth[i] > self.depth[j]:
    self.index[index_j] = index_i
    elif self.depth[i] < self.depth[j]:
    self.index[index_i] = index_j
    else:
    self.index[index_i] = index_j
    self.depth[index_j] += 1

    def __str__(self):
    return 'index: {}\ndepth: {}'.format(self.index, self.depth)
    7 changes: 7 additions & 0 deletions test.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,7 @@
    %%time

    js = DisjointSet(10)
    links = [[1,2], [2,3], [3,5], [5, 6]]
    for pair in links:
    js.union(pair[0], pair[1])
    print(js.tree_num())