Topological Sort

Use topological order when an item can be processed only after its prerequisites. Model prerequisite -> dependent: every edge must point forward in the resulting order. Such an order exists exactly when the directed graph is acyclic.

1. Recipe: Remove Nodes with No Remaining Prerequisites

This is Kahn's algorithm, called the peel-off recipe in the reference chapter. indegree[v] counts incoming edges from nodes not yet processed; the queue contains the unprocessed nodes whose count is zero.

from collections import deque

def topological_order(graph):
    indegree = [0] * len(graph)
    for neighbors in graph:
        for node in neighbors:
            indegree[node] += 1
    ready = deque(i for i, degree in enumerate(indegree) if degree == 0)
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                ready.append(neighbor)
    return order if len(order) == len(graph) else None

Choosing a zero-indegree node cannot violate a dependency. Removing its outgoing edges makes exactly the newly satisfied dependents available. If processing stops early, the remaining graph contains a cycle; a partial order is not a valid answer for the full graph. Include isolated vertices in the input. [] is a valid order for an empty graph; None signals a cycle here.

Each vertex is queued once and every edge is counted and removed once: $O(V+E)$ time, $O(V)$ auxiliary space, excluding the adjacency list. Keep duplicate edges consistent between adjacency lists and indegrees, or deduplicate both.

For Course Schedule II, input [course, prerequisite] becomes prerequisite -> course. Multiple orders may be valid. A min-heap of ready nodes gives the smallest available label first, with $O(E+V\log V)$ time. The order is unique exactly when there is only one ready choice at every step of a successful run.

2. Process a DAG in Dependency Order

Topological sorting is often only the preprocessing step. When processing u, all predecessors have already contributed, so its result is final and can be propagated along u -> v.

Skip unreachable nodes before doing arithmetic with sentinel values. These algorithms take $O(V+E)$ time and $O(V)$ result space; negative edge weights are allowed because there are no cycles. For path reconstruction, store parent[v]=u when a distance improves, then follow parents backward from the destination.

For example, edges A -> B, A -> C, B -> D, C -> D give two paths from A to D: ways[D] receives one contribution from each predecessor. This counts paths, not topological orderings.

For parallel tasks with duration duration[v], maintain earliest finish times: finish[v] = duration[v] + max(finish[u]) over prerequisites u; a source finishes at its own duration. The maximum finish time is the critical-path duration when resources are unlimited. With unit durations, processing ready nodes in batches gives the minimum number of dependency rounds, not the number of tasks.

3. Available Supplies Are Different from Zero Indegree

In Find All Possible Recipes, an ingredient with no prerequisites is not automatically available. Start with the supplies actually provided, map each ingredient to the recipes waiting for it, and count each recipe's unmet ingredients. When an ingredient becomes available, reduce its dependents' counts; a recipe reaching zero becomes a new supply.

Unknown ingredients remain unavailable. Publish each available item once so duplicate supply entries do not decrement counts twice. If empty ingredient lists are permitted, those recipes are initially available too. This is dependency propagation with external availability, rather than blindly enqueuing every zero-indegree string.

4. Key Takeaways

• Draw prerequisite -> dependent before coding; reversed edges can produce a plausible but reversed schedule.
• Verify the processed count equals V; one disconnected cycle invalidates a whole-graph ordering.
• On a DAG, use min, max, or addition in the same traversal to compute shortest paths, longest paths, or path counts.
• Resource availability is an input condition. A missing ingredient does not become available merely because nothing points into it.

Review Graphs for representation and cycles. Continue to Dynamic Programming to recognize implicit DAGs of subproblems, including increasing paths and sequence states.