Graph Algorithms: BFS, DFS & Topological Sort

from collections import deque

def bfs(graph: dict, start: int, target: int) -> int:
    """Returns shortest distance from start to target."""
    visited = {start}
    queue = deque([(start, 0)])  # (node, distance)

    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1  # not reachable

# For grid BFS:
DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
def bfs_grid(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    visited = {(start_r, start_c)}
    queue = deque([(start_r, start_c, 0)])
    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r+dr, c+dc
            if 0<=nr<rows and 0<=nc<cols and (nr,nc) not in visited and grid[nr][nc] != '#':
                visited.add((nr, nc))
                queue.append((nr, nc, dist+1))

def dfs_iterative(graph: dict, start: int) -> set:
    """Returns all nodes reachable from start."""
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

def has_cycle_directed(graph: dict) -> bool:
    """Cycle detection in directed graph using DFS + colors."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:  # back edge → cycle
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(dfs(n) for n in graph if color[n] == WHITE)

from collections import deque

def topological_sort(num_nodes: int, edges: list[list[int]]) -> list[int]:
    """
    Returns topological ordering or [] if cycle exists.
    Use case: Course Schedule, Task Dependencies, Build Order
    """
    graph = {i: [] for i in range(num_nodes)}
    in_degree = [0] * num_nodes

    for src, dst in edges:
        graph[src].append(dst)
        in_degree[dst] += 1

    # Start with all nodes that have no incoming edges
    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_nodes else []  # [] means cycle exists

import heapq

def dijkstra(graph: dict, start: int) -> dict:
    """
    Dijkstra's single-source shortest path.
    graph: {node: [(neighbor, weight), ...]}
    Returns: {node: shortest_distance_from_start}
    
    Time: O((V + E) log V) with binary heap
    Space: O(V)
    
    Requirement: ALL edge weights must be non-negative.
    Use Bellman-Ford if negative edges are possible.
    """
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # Min-heap: (distance, node)
    heap = [(0, start)]
    
    while heap:
        d, u = heapq.heappop(heap)
        
        # Skip if we've already found a better path
        if d > dist[u]:
            continue
        
        for v, weight in graph.get(u, []):
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    
    return dist

# For path reconstruction, track predecessors:
def dijkstra_with_path(graph: dict, start: int, end: int) -> tuple[int, list]:
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}
    heap = [(0, start)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        if u == end:
            break
        for v, w in graph.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    
    # Reconstruct path
    path, node = [], end
    while node is not None:
        path.append(node)
        node = prev[node]
    return dist[end], path[::-1]

class UnionFind:
    """
    Union-Find with path compression + union by rank.
    Nearly O(1) amortized per operation (O(α(n)), α = inverse Ackermann).
    
    Use cases:
    - Cycle detection in undirected graphs
    - Connected components (Kruskal's MST)
    - Grid connectivity (number of islands variant)
    - Dynamic connectivity queries
    """
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank   = [0] * n
        self.count  = n  # number of connected components

    def find(self, x: int) -> int:
        """Find root with PATH COMPRESSION — makes future finds O(1)."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """
        Union by RANK — attach smaller tree under root of taller tree.
        Returns True if x and y were in different components (edge added).
        Returns False if they were already connected (cycle detected).
        """
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # Already connected → adding edge would create cycle
        
        # Attach smaller rank tree under larger rank
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        
        self.count -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

# Example: Number of islands using Union-Find
def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)
    islands = sum(1 for r in range(rows) for c in range(cols) if grid[r][c] == '1')
    uf.count = islands  # only count land cells

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                for dr, dc in [(0, 1), (1, 0)]:  # right and down only
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        uf.union(r * cols + c, nr * cols + nc)

    return uf.count

# Cycle detection in undirected graph
def has_cycle_undirected(n: int, edges: list[list[int]]) -> bool:
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):  # False = already connected = cycle
            return True
    return False