Topological Sort and Cycle Detection

from collections import deque

def topo_sort(graph):
    """graph: {vertex: [successors]}. Returns an order, or None if cyclic."""
    indeg = {v: 0 for v in graph}
    for v in graph:
        for n in graph[v]:
            indeg[n] += 1

    q = deque(v for v in graph if indeg[v] == 0)   # ready immediately
    order = []

    while q:
        v = q.popleft()
        order.append(v)
        for n in graph[v]:
            indeg[n] -= 1          # one prerequisite satisfied
            if indeg[n] == 0:
                q.append(n)        # it just became ready

    return order if len(order) == len(graph) else None
    #                                              ↑ stuck: a cycle

import heapq

def topo_sort_lexicographic(graph):
    indeg = {v: 0 for v in graph}
    for v in graph:
        for n in graph[v]:
            indeg[n] += 1
    h = [v for v in graph if indeg[v] == 0]
    heapq.heapify(h)                      # ← the only change
    order = []
    while h:
        v = heapq.heappop(h)              # smallest ready vertex
        order.append(v)
        for n in graph[v]:
            indeg[n] -= 1
            if indeg[n] == 0:
                heapq.heappush(h, n)
    return order if len(order) == len(graph) else None

# O((V + E) log V) instead of O(V + E) — the price of determinism.

def topo_sort_dfs(graph):
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {v: WHITE for v in graph}
    order = []

    def visit(v):
        colour[v] = GREY                     # on the current path
        for n in graph[v]:
            if colour[n] == GREY:
                raise ValueError(f"cycle involving {n}")
            if colour[n] == WHITE:
                visit(n)
        colour[v] = BLACK
        order.append(v)                      # ← FINISH time, not start time

    for v in graph:
        if colour[v] == WHITE:
            visit(v)

    return order[::-1]                       # reverse finish order

def longest_path(graph, weights=None):
    """Longest path in a DAG. weights: {(u, v): cost}, default 1 per edge."""
    order = topo_sort(graph)
    if order is None:
        raise ValueError("not a DAG — longest path is undefined")

    dist = {v: 0 for v in graph}
    parent = {v: None for v in graph}

    for v in order:                  # ← in topological order, so dist[v] is final
        for n in graph[v]:
            w = weights.get((v, n), 1) if weights else 1
            if dist[v] + w > dist[n]:
                dist[n] = dist[v] + w
                parent[n] = v

    end = max(dist, key=dist.get)
    path = []
    while end is not None:
        path.append(end)
        end = parent[end]
    return path[::-1], max(dist.values())

tasks = {
    "design":   [("build", 5)],       # design takes 5 days, then build can start
    "build":    [("test", 10)],
    "test":     [("ship", 3)],
    "docs":     [("ship", 2)],
    "design2":  [("docs", 1)],
    "ship":     [],
}
# The longest path from any start to "ship" is the earliest possible
# ship date. Every task on it is critical; everything else has slack.

def find_cycle(graph):
    """Returns the actual cycle as a list, or None."""
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {v: WHITE for v in graph}
    stack = []

    def visit(v):
        colour[v] = GREY
        stack.append(v)
        for n in graph[v]:
            if colour[n] == GREY:
                i = stack.index(n)
                return stack[i:] + [n]      # ← the loop, spelled out
            if colour[n] == WHITE:
                found = visit(n)
                if found:
                    return found
        colour[v] = BLACK
        stack.pop()
        return None

    for v in graph:
        if colour[v] == WHITE:
            found = visit(v)
            if found:
                return found
    return None

# The GREY vertex is on the current path, so the path from where it first
# appears in `stack` up to now IS the cycle. That is why grey exists.