main.py

def derive_relations(derived_down, target, relations):
    for down, up in relations:
        if target == down:
            if (derived_down, up) in relations:
                continue
            if derived_down:
                relations.append((derived_down, up))
            derive_relations(target, up, relations)


class Comparable():
    transitive_relations = []

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        return (self.value, other.value) in self.transitive_relations

    def __gt__(self, other):
        return (other.value, self.value) in self.transitive_relations

    @staticmethod
    def set_transitive_relations(transitive_relations):
        Comparable.transitive_relations = transitive_relations

    def to_original(self):
        return self.value


def main(items, relations):
    transitive_relations = [*relations]
    for item in items:
        derive_relations(None, item, transitive_relations)


    Comparable.set_transitive_relations(transitive_relations)

    return [
        c.to_original() for c
        in sorted(map(Comparable, items))
    ]


if __name__ == '__main__':
    from datetime import datetime

    relations_1 = [(2, 4), (1, 0), (4, 1), (3, 2), (3, 0), (0, 5)]
    expected_1 = [3, 2, 4, 1, 0, 5]

    start = datetime.now()
    print(main(list(range(0, 6)), relations_1) == expected_1)
    print((datetime.now() - start).microseconds)

    relations_2 = [(18, 6), (15, 20), (3, 13), (3, 9), (5, 2), (12, 4), (14, 19), (8, 17), (15, 12), (0, 14), (19, 5), (2, 10), (1, 16), (19, 11), (3, 17), (1, 14), (15, 6), (9, 8), (11, 8), (11, 3), (6, 2), (19, 8), (4, 20), (18, 4), (19, 3), (16, 14), (20, 6), (5, 18), (15, 2), (11, 9), (19, 13), (18, 20), (17, 5), (18, 15), (20, 2), (18, 12), (7, 17), (0, 1), (14, 13), (5, 6), (13, 17), (13, 7), (8, 13), (0, 19), (15, 4), (3, 8), (19, 7), (19, 17)]
    expected_2 = [0, 1, 16, 14, 19, 11, 3, 9, 8, 13, 7, 17, 5, 18, 15, 12, 4, 20, 6, 2, 10]

    start = datetime.now()
    print(main(list(range(0, 21)), relations_2) == expected_2)
    print((datetime.now() - start).microseconds)

    relations_3 = [(9, 0), (14, 4), (9, 13), (13, 4), (2, 14), (10, 4), (1, 14), (7, 4), (0, 3), (2, 4), (1, 4), (0, 13), (3, 13), (0, 10), (8, 11), (8, 6), (3, 2), (0, 7), (0, 1), (0, 2), (14, 10), (14, 13), (7, 3), (13, 10), (1, 2), (0, 14), (3, 14), (1, 3), (6, 0), (6, 13), (0, 4), (7, 2), (3, 4), (6, 7), (12, 9), (11, 12), (5, 8), (12, 13), (11, 6), (1, 7), (6, 12), (7, 14)]
    expected_3 = [5, 8, 11, 6, 12, 9, 0, 1, 7, 3, 2, 14, 13, 10, 4]

    start = datetime.now()
    print(main(list(range(0, 15)), relations_3) == expected_3)
    print((datetime.now() - start).microseconds)

    relations_4 = [(8, 7), (12, 39), (24, 44), (23, 37), (28, 27), (6, 37), (46, 45), (22, 48), (21, 49), (26, 7), (28, 13), (12, 5), (9, 13), (17, 27), (15, 32), (37, 44), (16, 13), (9, 34), (2, 48), (41, 1), (16, 34), (27, 0), (40, 11), (20, 49), (1, 4), (41, 49), (29, 35), (45, 28), (8, 12), (3, 14), (9, 10), (29, 25), (16, 31), (48, 4), (20, 19), (43, 50), (31, 19), (26, 12), (5, 33), (1, 49), (48, 1), (50, 44), (47, 24), (27, 47), (9, 45), (13, 49), (16, 45), (42, 23), (48, 49), (29, 15), (42, 43), (45, 49), (47, 30), (16, 9), (29, 21), (36, 14), (43, 23), (10, 49), (49, 34), (45, 20), (39, 33), (20, 13), (38, 6), (31, 13), (9, 28), (42, 50), (12, 7), (17, 34), (33, 7), (9, 31), (16, 28), (31, 34), (47, 50), (5, 39), (17, 31), (19, 13), (9, 41), (41, 20), (19, 25), (38, 46), (26, 33), (25, 21), (31, 41), (29, 4), (45, 17), (3, 36), (14, 18), (6, 50), (33, 36), (4, 49), (45, 13), (9, 49), (15, 22), (16, 49), (46, 17), (24, 43), (10, 13), (32, 48), (47, 6), (34, 27), (8, 39), (42, 37), (19, 21), (47, 37), (0, 6), (20, 34), (41, 13), (35, 4), (8, 5), (11, 38), (46, 20), (25, 4), (0, 37), (24, 50), (26, 39), (7, 36), (2, 22), (43, 37), (47, 0), (20, 10), (31, 28), (41, 10), (6, 42), (42, 44), (35, 1), (32, 2), (26, 5), (19, 29), (37, 50), (30, 24), (10, 21), (48, 35), (13, 25), (16, 17), (25, 49), (43, 44), (7, 3), (5, 7), (19, 4), (28, 49), (12, 33), (1, 10), (46, 16), (46, 27), (45, 34), (48, 10), (10, 25), (44, 8), (24, 6), (31, 49), (28, 20), (9, 20), (45, 31), (16, 20), (46, 34), (16, 19), (24, 37), (32, 22), (17, 20), (1, 21), (19, 49), (31, 20), (46, 31), (39, 7), (8, 26), (10, 4), (5, 36), (48, 21), (41, 28), (24, 0), (4, 21)]
    expected_4 = [40, 11, 38, 46, 16, 9, 45, 17, 31, 41, 28, 20, 19, 29, 15, 32, 2, 22, 48, 35, 1, 10, 13, 25, 4, 21, 49, 34, 27, 47, 30, 24, 0, 6, 42, 43, 23, 37, 50, 44, 8, 26, 12, 5, 39, 33, 7, 3, 36, 14, 18]

    start = datetime.now()
    print(main(list(range(0, 51)), relations_4) == expected_4)
    print((datetime.now() - start).microseconds)