topo_lex.py

from collections import defaultdict
from graphlib import TopologicalSorter
from heapq import heappush, heappop, heapify


def topo_lex(pairs):
    deps = defaultdict(set)  # node -> set(dependencies)
    for a, b in pairs:
        deps.setdefault(a, set())
        deps[b].add(a)

    ts = TopologicalSorter(deps)
    ts.prepare()

    pq = list(ts.get_ready())
    heapify(pq)
    out = []
    while pq:
        n = heappop(pq)  # smallest ready node
        out.append(n)
        ts.done(n)
        for r in ts.get_ready():
            heappush(pq, r)

    if len(out) != len(deps):
        raise ValueError("cycle")
    return "".join(out)


pairs = [
    ("C", "A"),
    ("C", "F"),
    ("A", "B"),
    ("A", "D"),
    ("B", "E"),
    ("D", "E"),
    ("F", "E"),
]
assert topo_lex(pairs) == "CABDFE"

Nice, thanks. This was for 2018 - day 07 actually.