disjointset

gistfile1.py

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

set = {}

data = [(100, 200), (100, 300), (100, 400), (100, 500), (400, 600), (700, 500), (800, 800)]


def root(n):
    global set
    if n not in set:
        set[n] = n
        return n
    if set[n] == n:
        return n
    result = root(set[n])
    set[n] = result
    return result


def merge(a, b):
    global set
    ra, rb = root(a), root(b)
    if ra == rb:
        return
    set[ra] = rb


def main():
    global set
    for i, j in data:
        merge(i, j)
    result = {}

    for i, j in set.iteritems():
        r = root(j)
        if r in result:
            result[r].append(i)
        else:
            result[r] = [i]

    for i, j in result.iteritems():
        print j

if __name__ == '__main__':
    main()