dc_weighted_fast_union.py

with open('input_pairs.txt') as f:
    ids = {}
    sz = {}
    lines = f.readlines()
    for line in lines:
        p,q = [int(x) for x in line.split(' ')]
        if p not in ids:
            ids[p] = p
            sz[p] = 1
        if q not in ids:
            ids[q] = q
            sz[q] = 1
        i, j = p, q
        while i != ids[i]:
            i = ids[i]
        while j != ids[j]:
            j = ids[j]
        if i == j:
            continue
        if(sz[i] < sz[j]):
            ids[i] = j
            sz[j] += sz[i]
        else:
            ids[j] = i
            sz[i] += sz[j]
        print(p,q)