Union Find

Tags: [data_structure]

Wiki Link: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non overlapping) subsets. It supports two useful operations:

• Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its "representative"; by comparing the result of two Find operations, one can determine whether two elements are in the same subset.
• Union: Join two subsets into a single subset.

UnionFind with path compression, and union by rank

class UnionFind(object):
    def __init__(self, n, relations):
        self.uf = [x for x in xrange(n)]
        self.rank = [0 for _ in xrange(n)]

        for r in relations:
            self.union(r[0], r[1])

    def find(self, x):
        if self.uf[x] != self.uf[self.uf[x]]:
            self.uf[x] = self.find(self.uf[x])

        return self.uf[x]

    def union(self, x, y):
        xx = self.find(x)
        yy = self.find(y)

        if self.rank[xx] > self.rank[yy]:
            xx, yy = yy, xx

        if self.rank[xx] == self.rank[yy]:
            self.rank[yy] += 1

        self.uf[xx] = yy


if __name__ == '__main__':
    print 'Program is working'

    n = 10
    relations = ((4, 5), (8, 7), (5, 6), (7, 9), (0, 7))
    union_find = UnionFind(n, relations)

    for x in xrange(n):
        print '{}\'s leaser={}'.format(x, union_find.find(x))

    print '-' * 30
    print 'uf={}'.format(union_find.uf)

    print 'Program is end'

Revelation:

• Reference: http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part4.pdf
• Here we consider the rank is the height of the tree.
• Here we think the height of the tree which only has one node is 0.

Note:

• Time complexity as followings, reference: https://www.slideshare.net/WeiLi73/time-complexity-of-union-find-55858534![]\
• The log*(x) means the number of times you need to take log() of x to make the x down to 1.