spoj 21083. Lexicographically Smallest | LEXSTR

lexstr.py

import array


class unionfind:
    def __init__(self, n):
        self._length = n
        self._roots = array.array('L', [x for x in xrange(n)])
        self._weights = array.array('L', [1]*n)

    def __str__(self):
        return str(self._roots)

    def union(self, a, b):
        assert isinstance(a, int) and isinstance(b, int)
        assert a < self._length and b < self._length

        aroot = self.find(a)
        broot = self.find(b)
        if self._weights[aroot] > self._weights[broot]:
            self._roots[broot] = aroot
            self._weights[aroot] += self._weights[broot]
            self._weights[broot] = 0
        else:
            self._roots[aroot] = broot
            self._weights[broot] += self._weights[aroot]
            self._weights[aroot] = 0

    def connected(self, a, b):
        assert isinstance(a, int) and isinstance(b, int)
        assert a < self._length and b < self._length

        return self.find(a) == self.find(b)

    def find(self, a):
        assert isinstance(a, int)

        while self._roots[a] != a:
            self._roots[a] = self._roots[self._roots[a]]
            a = self._roots[a]

        return a

class maplist(object):
    def __init__(self, arr, indices):
        self.arr = arr
        self.ind = indices
    def __getitem__(self, i):
        return self.arr[self.ind[i]]

    def __setitem__(self, i, v):
        self.arr[self.ind[i]] = v

    def sort(self):
        for i, x in enumerate(sorted(self)):
            self.arr[self.ind[i]] = x

    def __len__(self):
        return len(self.ind)


def main():
    for _ in xrange(int(raw_input())):
        s = list(raw_input())
        n = int(raw_input())
        uf = unionfind(len(s))
        m = {}
        for x in xrange(n):
            a, b = map(int, raw_input().split())
            uf.union(a, b)
        for x in xrange(len(s)):
            t = uf.find(x)
            if t != x:
                try:
                    m[t].append(x)
                except:
                    m[t] = [x]
        for x in m:
            m[x].append(x)
            m[x].sort()
            v = maplist(s, m[x])
            v.sort()
        print ''.join(s)


main()