Constraints

• 1 <= number of discovered classes <= 10^5 in the general case, but your algorithm should be near-linear in the number of classes and dependencies
• Class names are unique
• Each dependency name is a string
• annotations may include 'component' and/or 'transactional'
• A cycle is resolvable only when every bean in that cycle has scope 'singleton' and injection_type 'setter'

Examples

Solution

def solution(classes):
    from heapq import heappush, heappop

    beans = {}
    component_order = []

    # Classpath scanning: only classes annotated with 'component' become beans.
    for item in classes:
        name, annotations, dependencies, injection_type, scope, has_interface, is_final = item
        ann = {a.lower() for a in annotations}
        if 'component' in ann:
            beans[name] = {
                'annotations': ann,
                'dependencies': list(dependencies),
                'injection_type': injection_type.lower(),
                'scope': scope.lower(),
                'has_interface': bool(has_interface),
                'is_final': bool(is_final),
            }
            component_order.append(name)

    # Failure priority 1: missing dependencies, checked in component input order.
    for name in component_order:
        for dep in beans[name]['dependencies']:
            if dep not in beans:
                return {'status': 'MISSING_DEPENDENCY', 'bean': name, 'dependency': dep}

    names = list(beans.keys())
    graph = {name: list(beans[name]['dependencies']) for name in names}

    # Tarjan's algorithm for SCCs.
    index = 0
    stack = []
    on_stack = set()
    indices = {}
    lowlink = {}
    sccs = []

    def strongconnect(v):
        nonlocal index
        indices[v] = index
        lowlink[v] = index
        index += 1
        stack.append(v)
        on_stack.add(v)

        for w in graph[v]:
            if w not in indices:
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif w in on_stack:
                lowlink[v] = min(lowlink[v], indices[w])

        if lowlink[v] == indices[v]:
            comp = []
            while True:
                w = stack.pop()
                on_stack.remove(w)
                comp.append(w)
                if w == v:
                    break
            comp.sort()
            sccs.append(comp)

    for name in names:
        if name not in indices:
            strongconnect(name)

    # Failure priority 2: unresolvable cycles.
    problematic = None
    for comp in sccs:
        has_cycle = len(comp) > 1 or (len(comp) == 1 and comp[0] in graph[comp[0]])
        if not has_cycle:
            continue

        resolvable = all(
            beans[b]['scope'] == 'singleton' and beans[b]['injection_type'] == 'setter'
            for b in comp
        )
        if not resolvable:
            if problematic is None or tuple(comp) < tuple(problematic):
                problematic = comp

    if problematic is not None:
        return {'status': 'CIRCULAR', 'beans': problematic}

    # Failure priority 3: proxy validation and proxy type selection.
    proxies = {}
    for name in component_order:
        bean = beans[name]
        if 'transactional' in bean['annotations']:
            if bean['has_interface']:
                proxies[name] = 'JDK'
            elif not bean['is_final']:
                proxies[name] = 'CGLIB'
            else:
                return {'status': 'UNPROXYABLE', 'bean': name}
        else:
            proxies[name] = 'NONE'

    # Build SCC DAG for deterministic creation order.
    comp_id = {}
    comp_members = []
    for i, comp in enumerate(sccs):
        comp_members.append(comp)
        for b in comp:
            comp_id[b] = i

    dag = [set() for _ in range(len(sccs))]
    indegree = [0] * len(sccs)

    # If bean depends on dep, dep's component must come before bean's component.
    for bean in names:
        to_comp = comp_id[bean]
        for dep in graph[bean]:
            from_comp = comp_id[dep]
            if from_comp != to_comp and to_comp not in dag[from_comp]:
                dag[from_comp].add(to_comp)
                indegree[to_comp] += 1

    heap = []
    for i, comp in enumerate(comp_members):
        if indegree[i] == 0:
            heappush(heap, (comp[0], i))

    order = []
    while heap:
        _, cid = heappop(heap)
        order.extend(comp_members[cid])

        for nxt in sorted(dag[cid], key=lambda x: comp_members[x][0]):
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                heappush(heap, (comp_members[nxt][0], nxt))

    return {'status': 'OK', 'order': order, 'proxies': proxies}

Time complexity: O(V + E). Space complexity: O(V + E).

Hints

1. Model beans and dependencies as a directed graph. Strongly connected components help identify cycles.
2. After collapsing each strongly connected component into one node, the remaining graph is a DAG that can be topologically sorted.