Graph Algorithms

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    """Shortest paths from start to all nodes - O((V+E) log V)"""
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]   # Min-heap: (distance, node)
    
    while pq:
        dist, node = heapq.heappop(pq)  # Process closest unvisited node
        
        if dist > distances[node]:       # LAZY DELETION: skip stale entries
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = dist + weight     # RELAX: can we reach neighbor faster via node?
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    
    return distances

def bellman_ford(n, edges, start):
    """Handles negative weights, detects negative cycles - O(VE)"""
    distances = [float('inf')] * n
    distances[start] = 0
    
    # Relax all edges V-1 times -- each iteration extends paths by one edge
    for _ in range(n - 1):
        for u, v, w in edges:
            if distances[u] != float('inf') and distances[u] + w < distances[v]:
                distances[v] = distances[u] + w
    
    # NEGATIVE CYCLE CHECK: one more pass -- if any distance improves,
    # a negative cycle is reachable from the source
    for u, v, w in edges:
        if distances[u] != float('inf') and distances[u] + w < distances[v]:
            return None  # Negative cycle exists
    
    return distances

from collections import deque, defaultdict

def topological_sort(n, prerequisites):
    """Return valid ordering or empty list if cycle exists"""
    graph = defaultdict(list)
    in_degree = [0] * n
    
    # Build adjacency list and compute in-degrees
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Seed queue with all nodes that have no prerequisites (in-degree 0)
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1       # "Remove" this edge
            if in_degree[neighbor] == 0:   # All prerequisites satisfied
                queue.append(neighbor)
    
    # If result is shorter than n, a cycle prevented some nodes from being processed
    return result if len(result) == n else []

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # Each node is its own root initially
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # PATH COMPRESSION
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # Already in the same component -- adding edge would create cycle
        # UNION BY RANK: attach smaller tree under larger tree
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    """Find minimum spanning tree - O(E log E)"""
    # GREEDY: sort edges by weight (cheapest first)
    edges.sort(key=lambda x: x[2])
    
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    for u, v, weight in edges:
        if uf.union(u, v):              # Only add if it connects two different components
            mst.append((u, v, weight))
            total_weight += weight
            if len(mst) == n - 1:       # MST has exactly V-1 edges
                break
    
    return mst, total_weight