"""fan-out unit 의존 그래프: 위상정렬 + 순환검출 (Kahn, id 사전순 결정적)."""
from __future__ import annotations


class CycleError(ValueError):
    """depends-on 그래프에 순환이 있을 때."""


def topological_order(units: dict[str, list[str]]) -> list[str]:
    """unit-id 를 착수 가능한 순서(의존 먼저)로 반환.

    units: unit-id -> 그 unit 이 의존하는 unit-id 목록.
    순환이면 CycleError, 알 수 없는 의존이면 ValueError.
    """
    # 같은 의존을 두 번 적으면(`depends-on: a, a`) indegree 와 감소 횟수가 어긋나
    # 순환이 없는데도 CycleError 가 난다. unit 별 의존을 dedupe 해 일치시킨다.
    dep_sets = {u: set(deps) for u, deps in units.items()}
    indeg = {u: 0 for u in units}
    for u, deps in dep_sets.items():
        for d in deps:
            if d not in units:
                raise ValueError(f"unit {u!r} depends on unknown unit {d!r}")
            indeg[u] += 1
    queue = sorted(u for u, n in indeg.items() if n == 0)
    order: list[str] = []
    while queue:
        u = queue.pop(0)
        order.append(u)
        for v, deps in dep_sets.items():
            if u in deps:
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)
        queue.sort()
    if len(order) != len(units):
        remaining = sorted(set(units) - set(order))
        raise CycleError(f"dependency cycle among units: {remaining}")
    return order