¿Cómo resolver Course Schedule II con ordenamiento topológico?

Enunciado y alcance

Hay num_courses cursos etiquetados de 0 a num_courses - 1. Un par de prerrequisito [course, prerequisite] significa que prerequisite debe completarse antes de course. Devuelve cualquier orden que complete todos los cursos. Devuelve una lista vacía si no existe tal orden.

Para esta versión, asume 0 <= num_courses <= 2000, que cada etiqueta de curso es válida, que los pares son distintos y que la entrada no contiene auto-bucles (self-edges). Devuelve una lista vacía cuando num_courses == 0. Para num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]], tanto [0, 1, 2, 3] como [0, 2, 1, 3] son correctos. Para [[1, 0], [0, 1]], los dos cursos dependen el uno del otro, por lo que la única respuesta válida es una lista vacía.

Este es un problema de codificación representativo de ingeniería de software general. Su tarea central es traducir dependencias en lenguaje natural a un grafo dirigido y decidir si dicho grafo es acíclico. El problema base solicita cualquier orden válido. No pide el orden lexicográficamente menor, duraciones de cursos ni un límite de cursos simultáneos.

Qué evalúa el entrevistador

La primera señal es la dirección de las aristas. [course, prerequisite] se convierte en prerequisite -> course, porque completar el prerrequisito habilita el curso. Un grafo invertido aún puede producir una permutación, pero esa permutación codifica la restricción opuesta.

La segunda señal es si el candidato puede derivar el grado de entrada (indegree) a partir de la frase "curso actualmente disponible". El grado de entrada de un curso es la cantidad de prerrequisitos directos que aún no se han cumplido. Solo un curso con grado de entrada cero está listo. Completar un curso decrementa únicamente los grados de entrada de sus sucesores directos. Una respuesta sólida explica este estado en lugar de limitarse a decir "usar BFS".

La tercera señal es la detección de ciclos. Una cola vacía no justifica devolver una respuesta parcial. Todos los nodos se procesaron únicamente cuando la longitud del resultado es igual a la cantidad de cursos. Un resultado más corto significa que el subgrafo restante no tiene ningún nodo con grado de entrada cero y debe contener un ciclo dirigido.

El entrevistador también evaluará la complejidad, los casos límite y la disciplina del contrato. Una implementación con listas de adyacencia utiliza tiempo y espacio O(V + E). deque.popleft() mantiene la extracción desde el frente de la cola en tiempo constante. Las pruebas deben cubrir múltiples órdenes válidos, cursos desconectados, entrada vacía y una cadena larga de dependencias.

Preguntas clarificadoras antes de responder

• ¿Puedo devolver cualquier orden o debe ser el lexicográficamente menor? Una cola normal devuelve cualquier

orden. El orden menor requiere un min-heap y cambia la cota de tiempo a O(E + V log V).

• ¿Pueden repetirse los pares de prerrequisitos? Este problema indica que son distintos. Si pudieran repetirse, se deben

mantener entradas de adyacencia duplicadas y contar ambas en el grado de entrada, o bien desduplicar ambas estructuras al construir el grafo. Desduplicar solo un lado hace que los conteos sean inconsistentes.

• ¿Las etiquetas pueden ser inválidas o la entrada contener auto-aristas? El problema base asume una entrada

validada. Una API defensiva debería distinguir una solicitud inválida de un grafo válido que contiene un ciclo, en lugar de mapear silenciosamente ambos casos a una lista vacía.

• ¿Necesitamos un solo orden o todos los órdenes válidos? Encontrar un orden es un recorrido lineal de grafos.

Enumerar cada orden se ramifica sobre todos los nodos actualmente disponibles y puede producir casi tantos resultados como un factorial.

• ¿Los cursos pueden realizarse en paralelo? El resultado base es un orden lineal. Con capacidad ilimitada por

semestre, el número mínimo de semestres requiere procesamiento de la cola nivel por nivel. Con duraciones de cursos, el problema se convierte en el cálculo del camino más largo en un DAG.

• ¿El grafo cabe en memoria? Una lista de adyacencia es directa para V <= 2000. El almacenamiento

externo o el procesamiento particionado sería un problema de sistemas diferente.

Estructura de respuesta de 30 segundos

"Modelaré cada curso como un nodo y transformaré [course, prerequisite] en una arista desde el prerrequisito hacia el curso. También contaré el grado de entrada de cada curso. Pondré cada curso con grado de entrada cero en una cola, retiraré repetidamente uno hacia el resultado, decrementaré los grados de entrada de sus sucesores y encolaré un sucesor cuando su grado de entrada llegue a cero. La cola contiene exactamente los cursos no procesados cuyos prerrequisitos ya están completos, por lo que cada elección es segura. Si el resultado contiene todos los cursos, lo devuelvo; de lo contrario, los nodos restantes contienen un ciclo, por lo que devuelvo una lista vacía. Con una lista de adyacencia, tanto el tiempo como el espacio adicional son O(V + E)".

Análisis paso a paso a profundidad

Una solución directa escanea repetidamente cada curso no seleccionado y elige uno cuyos prerrequisitos ya hayan aparecido. Incluso con un conjunto de cursos completados, cada ronda puede inspeccionar cada arista. Una cadena puede requerir V rondas, haciendo que el peor caso sea O(VE). El recálculo continuo de dependencias satisfechas es el cuello de botella.

El algoritmo de Kahn mantiene esa información de manera incremental como grado de entrada. Sea graph[u] el contenedor de los cursos que pueden liberarse tras completar u, y sea indegree[v] el contador de los prerrequisitos directos de v que restan. Para cada [course, prerequisite], añadimos course a graph[prerequisite] e incrementamos indegree[course].

El algoritmo mantiene dos invariantes:

1. indegree[v] es igual a la cantidad de aristas dirigidas hacia v provenientes de nodos no procesados.
2. La cola contiene única y exclusivamente los cursos no procesados cuyo grado de entrada restante es cero.

El conteo inicial satisface el primer invariante, y encolar cada nodo con grado de entrada cero establece el segundo. Cuando se retira el curso u, ningún prerrequisito sin procesar apunta hacia él, por lo que añadirlo al resultado es seguro. Retirar u se representa visitando graph[u] y decrementando el grado de entrada de cada sucesor. Un sucesor se encola exactamente cuando su conteo llega a cero por primera vez, preservando ambos invariantes.

from collections import deque


def find_course_order(
    num_courses: int,
    prerequisites: list[list[int]],
) -> list[int]:
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        indegree[course] += 1

    ready = deque(
        course for course, degree in enumerate(indegree) if degree == 0
    )
    order: list[int] = []

    while ready:
        course = ready.popleft()
        order.append(course)

        for dependent in graph[course]:
            indegree[dependent] -= 1
            if indegree[dependent] == 0:
                ready.append(dependent)

    return order if len(order) == num_courses else []

Si se procesan todos los cursos, los invariantes garantizan que todos sus prerrequisitos aparecieron antes, por lo que el resultado es válido. Si el resultado es más corto que V, cada nodo en el subgrafo finito restante tiene un grado de entrada positivo. Al comenzar en cualquier nodo restante y seguir repetidamente una arista entrante, un grafo finito eventualmente debe repetir un nodo, y el segmento repetido es un ciclo dirigido. Por lo tanto, no existe ningún orden completo. La verificación de longitud es también la prueba de ciclo.

Cada nodo entra y sale de la cola como máximo una vez. Cada arista se maneja una vez al construir el grafo y una vez al liberar sucesores, por lo que el tiempo es O(V + E). La lista de adyacencia, el arreglo de grados de entrada, la cola y el resultado usan O(V + E) de espacio. La implementación utiliza deque porque el list.pop(0) de Python desplaza los elementos restantes y puede hacer que una operación de cola sea lineal.

La validación adversarial debe verificar propiedades en lugar de una única respuesta fija. Un resultado exitoso debe contener exactamente V etiquetas únicas, y la posición de prerequisite debe ser menor que la posición de course para cada par. Debe cubrir un grafo vacío, un solo nodo, nodos todos independientes, una cadena larga, un diamante con múltiples órdenes, componentes desconectados y un ciclo dirigido. El caso del diamante detecta pruebas que exigen incorrectamente un orden topológico en particular.

DFS también puede calcular un orden topológico. Usa estados blanco, gris y negro; una arista hacia un nodo gris detecta un ciclo, y los nodos ingresan al resultado en la salida recursiva antes de invertir el postorden. DFS es útil cuando la API también debe reportar un ciclo concreto, pero una cadena larga puede exceder el límite de recursión de Python. El algoritmo de Kahn expone el conjunto de cursos disponibles actualmente y se extiende de forma natural a semestres paralelos, por lo que es la opción más directa aquí. Para un grafo diminuto donde solo importa la viabilidad, el escaneo repetido puede ser más corto; declara su costo en el peor de los casos en lugar de llamarlo lineal.

Respuesta de muestra de alta calidad

"Primero confirmaré que cualquier orden válido es aceptable y asumiré que las etiquetas y las aristas distintas son válidas. Cada par [course, prerequisite] crea una arista desde el prerrequisito hacia el curso. El grado de entrada de un curso mide cuántos prerrequisitos directos siguen incompletos.

Construyo una lista de adyacencia y un arreglo de grados de entrada, luego agrego cada curso con grado de entrada cero a un deque. En el bucle, retiro un curso hacia la respuesta y decremento los grados de entrada de sus sucesores. Un sucesor se encola solo cuando su grado de entrada llega a cero. El invariante clave es que la cola contiene exactamente los cursos sin prerrequisitos pendientes, por lo que elegir de ella no puede violar una arista.

No puedo devolver incondicionalmente cuando la cola se vacía. Si la longitud de la respuesta es igual a la cantidad de cursos, se satisfizo cada dependencia. Si es más corta, todos los nodos restantes aún tienen una arista entrante. Seguir aristas entrantes en un grafo finito inevitablemente revisita un nodo, lo que demuestra que permanece un ciclo, por lo que devuelvo una lista vacía.

La lista de adyacencia procesa cada nodo y arista una cantidad constante de veces, resultando en tiempo O(V + E) y espacio O(V + E). Probaría con un grafo vacío, un nodo, una cadena larga, un diamante con múltiples respuestas, componentes desconectados y un ciclo de dos nodos. Para respuestas múltiples, valido la posición relativa de cada prerrequisito en lugar de comparar con un arreglo fijo".

Errores comunes

• Construir course -> prerequisite → un curso puede aparecer antes de su prerrequisito → **Construir

prerequisite -> course, siguiendo la pregunta '¿qué libera completar este nodo?'**

• Comenzar solo desde el curso 0 → los componentes desconectados desaparecen → **Escanear todos los nodos y encolar

cada nodo inicial con grado de entrada cero.**

• Devolver un resultado parcial cuando la cola se vacía → una entrada cíclica se reporta como exitosa → **Devolver

un orden solo cuando len(order) == num_courses.**

• Encolar un nodo más de una vez → el resultado contiene cursos duplicados → **Encolar únicamente en la

transición del grado de entrada de 1 a 0.**

• Usar list.pop(0) como la cola → entradas grandes desplazan repetidamente elementos → **Usar

deque.popleft().**

• Comparar la salida con un solo orden topológico fijo → otro orden válido falla la prueba → **Verificar

unicidad, longitud y las posiciones relativas de cada arista.**

• Desduplicar el grafo pero no el grado de entrada, o viceversa → los conteos no coinciden bajo un contrato con aristas

duplicadas → Mantener duplicados de manera consistente o desduplicar cada arista durante la construcción del grafo.

• Afirmar espacio adicional O(V) → la lista de adyacencia aún almacena todas las aristas → **Reportar O(V + E) para

esta representación de grafo disperso.**

• Usar DFS sin un estado en progreso → los nodos en ciclos entran en recursión repetidamente o terminan incorrectamente →

Usar al menos tres estados para separar nodos activos y completados.

Preguntas de seguimiento y cómo abordarlas

Pregunta de seguimiento 1: ¿Cómo devolverías el orden válido lexicográficamente menor?

Reemplaza la cola con un min-heap. Tomar la etiqueta más pequeña entre todos los nodos actualmente disponibles da el resultado lexicográficamente menor mediante un argumento de intercambio voraz (greedy). El trabajo de aristas sigue siendo O(E), mientras que la inserción y extracción del heap hacen que el total sea O(E + V log V). Una cola normal sigue siendo más simple y rápida cuando se acepta cualquier orden.

Pregunta de seguimiento 2: Con cursos paralelos ilimitados por semestre, ¿cuál es la cantidad mínima de semestres?

Procesa la cola por el tamaño de su nivel actual. Los cursos en un nivel se completan en el mismo semestre, y sus sucesores recién liberados con grado de entrada cero forman el siguiente nivel. Incrementa el conteo de semestres por nivel. Esto funciona solo cuando todos los cursos toman el mismo tiempo y la capacidad del semestre es ilimitada. Un límite de a lo sumo k cursos por semestre hace que el procesamiento simple por niveles sea insuficiente para una optimalidad global.

Pregunta de seguimiento 3: Los cursos tienen diferentes duraciones. ¿Cómo encuentras el tiempo más temprano de graduación?

Primero obtén un orden topológico y luego ejecuta programación dinámica en ese orden. El inicio más temprano de un curso es el tiempo de finalización más temprano máximo entre sus prerrequisitos; suma su propia duración para obtener su finalización más temprana. La respuesta es el tiempo de finalización máximo. Los niveles de Kahn no bastan porque un curso de diez semanas y uno de una semana no pueden tratarse como unidades iguales.

Pregunta de seguimiento 4: ¿Cómo devolverías un ciclo de dependencias concreto?

El algoritmo de Kahn demuestra que el subgrafo restante tiene un ciclo, pero no conserva su ruta. Ejecuta un DFS de tres colores en los nodos restantes y almacena punteros al padre. En una arista hacia un nodo gris, sigue los padres hacia atrás para reconstruir el ciclo. Si el diagnóstico es un requisito principal, se puede usar un ordenamiento topológico por DFS con rastreo de padres desde el inicio.

Pregunta de seguimiento 5: ¿Cómo mantendrías un orden a medida que se agregan aristas de prerrequisitos?

Para actualizaciones poco frecuentes, volver a ejecutar el algoritmo O(V + E) después de cada inserción es lo más confiable y fácil de verificar. Para un grafo grande con actualizaciones frecuentes, almacena la posición actual de cada nodo. Una arista que ya es consistente con ese orden no necesita cambios; una arista inconsistente requiere verificación de alcanzabilidad y reordenamiento dentro del intervalo afectado. El ordenamiento topológico dinámico es complejo, por lo que su costo debe justificarse con el tamaño medido del grafo y la tasa de actualización.

Pregunta de seguimiento 6: ¿Cómo enumerarías todos los órdenes de cursos válidos?

Usa backtracking. En cada paso, ramifícate sobre todos los nodos actuales con grado de entrada cero, elige uno temporalmente, actualiza sus sucesores, haz la recursión y restaura los grados de entrada. Esto evita permutaciones inválidas, pero el número de órdenes válidos puede acercarse a V!, por lo que el tiempo de ejecución es al menos proporcional a la salida. Confirma un límite pequeño primero y pregunta si quien llama realmente necesita un conteo, una muestra o solo los primeros k órdenes.