py_graph_cycle_detector

Código comentado línea a línea y paso a paso:

Entregas: py_graph_cycle_detector.py con py_graph_cycle_detector(graph). Rank 05 · nivel 2.

Qué pide (en palabras normales)

Subject (enunciado original)
Write a function that determines whether a directed graph contains at least one cycle.

The function takes a dictionary representing an adjacency list where keys are integer node IDs and values are lists of integer neighbor node IDs.

The function should:
- Return True if the directed graph contains a cycle.
- Return False if the graph is acyclic or if the input graph dictionary is empty.
- Correctly handle graphs with multiple disconnected components.

Expected file: py_graph_cycle_detector.py
Function signature:
def py_graph_cycle_detector(graph: dict[int, list[int]]) -> bool:
Forbidden: graphlib.TopologicalSorter

Examples:
py_graph_cycle_detector({0: [1], 1: [2], 2: [0]})
=> True
py_graph_cycle_detector({0: [1], 1: [2], 2: []})
=> False
py_graph_cycle_detector({})
=> False

La idea: tres colores

state = {}            # sin entrada: no visto · 1: en el camino actual · 2: terminado

def visit(node):
    if state.get(node) == 1:   # ¡vuelvo a un nodo que aún no he cerrado! → ciclo
        return True
    if state.get(node) == 2:   # ya explorado y limpio
        return False
    state[node] = 1
    for nxt in graph.get(node, []):
        if visit(nxt):
            return True
    state[node] = 2
    return False

En un grafo dirigido, "ya visitado" no basta: dos caminos distintos pueden llegar al mismo nodo sin ciclo (un rombo). El ciclo solo existe si vuelvo a un nodo que sigue en mi camino actual (estado 1). Por eso tres estados y no un set.

Arrancar desde todos

for node in graph:
    if visit(node):
        return True
return False

Si el grafo tiene varias componentes, un solo arranque no las recorre todas. Los nodos ya terminados (2) salen al instante, así no repito trabajo.

Trampas