tc - 516 div2 - 1000 (py)

NetworkXMessageRecovery.py

#!/usr/bin/env python
"""(c) gorlum0 [at] gmail.com"""
import itertools as it
from sys import stdin

class NetworkXMessageRecovery:
    def recover(self, messages):
        res = []

        req = {}
        for msg in messages:
            for c in msg:
                if c not in req: req[c] = set([])
        for msg in messages:
            for i, a in enumerate(msg):
                req[a].update(msg[:i])

        while req:
            best = min(k for k in req if not req[k])
            res.append(best)
            for k in req: req[k].discard(best)
            del req[best]

        return ''.join(res)

def main():
    for line in stdin:
        n = int(line)
        ## messages = [next(stdin).strip() for _ in xrange(n)]
        messages = [l.strip() for l in it.islice(stdin, n)]

        print NetworkXMessageRecovery().recover(messages)

if __name__ == '__main__':
    main()