Graph Algorithms

def build_undirected_graph(num_nodes, edges):
    """edges is a list of [u, v] pairs."""
    neighbors = {node: [] for node in range(num_nodes)}

    for u, v in edges:
        neighbors[u].append(v)
        neighbors[v].append(u)   # both directions - THIS is the forgotten line

    return neighbors


def build_directed_graph(num_nodes, edges):
    """edges is a list of [before, after] pairs: 'before' points at 'after'."""
    neighbors = {node: [] for node in range(num_nodes)}

    for before, after in edges:
        neighbors[before].append(after)   # one direction only

    return neighbors


def build_weighted_graph(num_nodes, edges):
    """edges is a list of [u, v, weight]. Store the weight alongside the neighbor."""
    neighbors = {node: [] for node in range(num_nodes)}

    for u, v, weight in edges:
        neighbors[u].append((v, weight))
        neighbors[v].append((u, weight))

    return neighbors

import heapq

def dijkstra(num_nodes, neighbors, source):
    """neighbors[node] is a list of (other_node, weight) pairs."""
    INFINITY = float('inf')
    distance = [INFINITY] * num_nodes
    distance[source] = 0

    frontier = [(0, source)]        # min-heap of (distance_so_far, node)

    while frontier:
        dist_to_node, node = heapq.heappop(frontier)

        # A node gets pushed again every time we find a cheaper route to it,
        # so old entries linger. If this one is worse than what we already
        # know, it is stale - drop it.
        if dist_to_node > distance[node]:
            continue

        # Popping the heap minimum with no negative weights means
        # distance[node] can never improve again. It is final now.
        for other_node, weight in neighbors[node]:
            candidate = dist_to_node + weight
            if candidate < distance[other_node]:
                distance[other_node] = candidate
                heapq.heappush(frontier, (candidate, other_node))

    return distance

def bellman_ford(num_nodes, edges, source):
    """edges is a list of (u, v, weight); weights may be negative.
       Returns None if a negative cycle is reachable from the source."""
    INFINITY = float('inf')
    distance = [INFINITY] * num_nodes
    distance[source] = 0

    # A shortest path visits at most num_nodes - 1 edges, and each round
    # extends every correct answer by one more edge.
    for _ in range(num_nodes - 1):
        something_improved = False
        for u, v, weight in edges:
            if distance[u] == INFINITY:
                continue
            if distance[u] + weight < distance[v]:
                distance[v] = distance[u] + weight
                something_improved = True
        if not something_improved:
            break                   # already stable, no point continuing

    # One extra round: if anything STILL improves, a negative cycle exists.
    for u, v, weight in edges:
        if distance[u] != INFINITY and distance[u] + weight < distance[v]:
            return None

    return distance

def find_cheapest_price(num_cities, flights, source, target, k):
    INFINITY = float('inf')
    cost = [INFINITY] * num_cities
    cost[source] = 0

    # "At most k stops" means at most k + 1 flights, so k + 1 rounds.
    for _ in range(k + 1):
        cost_before_this_round = cost[:]      # freeze - see callout above

        for start, end, price in flights:
            if cost_before_this_round[start] == INFINITY:
                continue
            candidate = cost_before_this_round[start] + price
            if candidate < cost[end]:
                cost[end] = candidate

    return cost[target] if cost[target] != INFINITY else -1

import heapq

def minimum_effort_path(heights):
    rows, cols = len(heights), len(heights[0])
    INFINITY = float('inf')
    best_effort = [[INFINITY] * cols for _ in range(rows)]
    best_effort[0][0] = 0

    frontier = [(0, 0, 0)]      # (effort so far, row, col)

    while frontier:
        effort, row, col = heapq.heappop(frontier)

        if row == rows - 1 and col == cols - 1:
            return effort       # popped the target: this value is final

        if effort > best_effort[row][col]:
            continue            # stale entry

        for d_row, d_col in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_row, next_col = row + d_row, col + d_col
            if not (0 <= next_row < rows and 0 <= next_col < cols):
                continue

            step = abs(heights[next_row][next_col] - heights[row][col])
            # The cost of a path is its WORST step, not the sum of its steps.
            candidate = max(effort, step)

            if candidate < best_effort[next_row][next_col]:
                best_effort[next_row][next_col] = candidate
                heapq.heappush(frontier, (candidate, next_row, next_col))

    return 0

from collections import deque

def find_order(num_courses, prerequisites):
    neighbors = {course: [] for course in range(num_courses)}
    in_degree = [0] * num_courses

    for course, needs_first in prerequisites:
        neighbors[needs_first].append(course)   # needs_first unlocks course
        in_degree[course] += 1

    queue = deque()
    for course in range(num_courses):
        if in_degree[course] == 0:
            queue.append(course)

    order = []
    while queue:
        course = queue.popleft()
        order.append(course)
        for unlocked in neighbors[course]:
            in_degree[unlocked] -= 1
            if in_degree[unlocked] == 0:
                queue.append(unlocked)

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

from collections import deque

def alien_order(words):
    neighbors = {}
    in_degree = {}
    for word in words:
        for char in word:
            neighbors.setdefault(char, [])
            in_degree.setdefault(char, 0)

    for first, second in zip(words, words[1:]):
        # "abc" before "ab" is impossible in any alphabet: a prefix must
        # come first. This case yields no edge, it yields an error.
        if len(first) > len(second) and first.startswith(second):
            return ""

        for char_a, char_b in zip(first, second):
            if char_a != char_b:
                neighbors[char_a].append(char_b)
                in_degree[char_b] += 1
                break        # only the FIRST difference tells us anything

    queue = deque()
    for char in in_degree:
        if in_degree[char] == 0:
            queue.append(char)

    order = []
    while queue:
        char = queue.popleft()
        order.append(char)
        for next_char in neighbors[char]:
            in_degree[next_char] -= 1
            if in_degree[next_char] == 0:
                queue.append(next_char)

    if len(order) != len(in_degree):
        return ""            # cycle: the ordering contradicts itself

    return "".join(order)

from collections import deque

def find_min_height_trees(num_nodes, edges):
    if num_nodes == 1:
        return [0]

    neighbors = {node: set() for node in range(num_nodes)}
    for u, v in edges:
        neighbors[u].add(v)
        neighbors[v].add(u)

    leaves = deque()
    for node in range(num_nodes):
        if len(neighbors[node]) == 1:
            leaves.append(node)

    remaining = num_nodes
    while remaining > 2:
        # Peel exactly one full layer of leaves per iteration.
        layer_size = len(leaves)
        remaining -= layer_size

        for _ in range(layer_size):
            leaf = leaves.popleft()
            parent = neighbors[leaf].pop()
            neighbors[parent].discard(leaf)
            if len(neighbors[parent]) == 1:
                leaves.append(parent)

    return list(leaves)