Union find

unionfind.py

# -*- coding: utf-8 -*-

class UnionFind:
    def __init__(self):
        self.refs = {}

    def find(self, x):
        if x in self.refs:
            ref = self.find(self.refs[x])
            self.refs[x] = ref
            return ref
        else:
            return x

    def unify(self, x, y):
        X = self.find(x)
        Y = self.find(y)

        if X == Y:
            return
        else:
            self.refs[X] = Y