Graph Algorithms — Shortest Path, MST, Topological Sort¶

import heapq

def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
    """
    graph: adjacency list {node: [(neighbor, weight), ...]}
    Returns: shortest distance from start to every reachable node.
    Requires non-negative weights — a negative edge can invalidate the
    greedy "once popped, final" guarantee.
    """
    dist = {start: 0}
    heap = [(0, start)]  # (distance, node)
    visited = set()

    while heap:
        d, node = heapq.heappop(heap)
        if node in visited:
            continue  # stale entry (we don't support decrease-key, so skip)
        visited.add(node)

        for neighbor, weight in graph.get(node, []):
            nd = d + weight
            if nd < dist.get(neighbor, float("inf")):
                dist[neighbor] = nd
                heapq.heappush(heap, (nd, neighbor))

    return dist
    # Time: O((V + E) log V) — each edge may push once, heap ops are O(log V)
    # Space: O(V + E) — this is the LAZY-DELETION variant (no decrease-key
    # support, stale heap entries just get skipped via the `visited` check
    # above), so the heap can hold up to one entry per edge relaxation,
    # not just one per vertex. dist/visited are O(V); heap is O(E) in the
    # worst case (a dense graph where most nodes get relaxed repeatedly
    # before settling) — the combined bound is commonly simplified to
    # O(E) since E >= V-1 for a connected graph. A decrease-key-based
    # implementation (using an indexed/updatable heap) would cap the
    # heap at O(V) entries instead, at the cost of a more complex heap
    # structure than Python's stdlib heapq provides out of the box.

import heapq

def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    """Signal sent from node k — time for it to reach all n nodes, or -1."""
    graph: dict[int, list[tuple[int, int]]] = {}
    for u, v, w in times:
        graph.setdefault(u, []).append((v, w))

    dist = {k: 0}
    heap = [(0, k)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float("inf")):
            continue
        for neighbor, weight in graph.get(node, []):
            nd = d + weight
            if nd < dist.get(neighbor, float("inf")):
                dist[neighbor] = nd
                heapq.heappush(heap, (nd, neighbor))

    return max(dist.values()) if len(dist) == n else -1
    # Time: O((V+E) log V)

from collections import deque

def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """Return a valid course order, or [] if impossible (cycle)."""
    graph = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return order if len(order) == num_courses else []
    # Time: O(V + E)

def min_cost_connect_points(points: list[list[int]]) -> int:
    """Manhattan-distance MST over n points — classic Kruskal on a dense-ish graph."""
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((dist, i, j))
    edges.sort()

    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total, used = 0, 0
    for dist, i, j in edges:
        ri, rj = find(i), find(j)
        if ri != rj:
            parent[ri] = rj
            total += dist
            used += 1
            if used == n - 1:
                break

    return total
    # Time: O(V² log V) dominated by sorting O(V²) edges — fine for this problem's constraints