siavashk

# https://leetcode.com/discuss/post/2371234/an-opinionated-guide-to-binary-search-co-1yfw/
def minimization(arr, condition):
    """
    Find the first time a condition is True.
    [F, F, F, (T), T, T, T]
    (T) is the first time the conditions is True.
    r is the True answer (always T)
    l is always invalid (always F)
    """
    l, r = -1, len(arr) - 1 # if len(arr) is a candidate

siavashk

# UnionFind is defined in https://gist.github.com/siavashk/fef678f9f2ef17fdc6cff917922bf4ba
# Augment the union function to return True for new connections
def kruskal(edges: list[tuple[int, int, int]]):
    """ 
    Edges: list of edge in (weight, start, end]) format

    """
    edges.sort()
    uf = UnionFind()
    for _, x, y in edges:

siavashk

def bellman_ford(n, edges, src):
    dist = [float("inf")] * n
    dist[src] = 0

    for _ in range(n - 1):
        for u, v, weight in edges:
            if dist[u] != float("inf") and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight

    for u, v, weight in edges:

siavashk

import heapq


def iterative_minimum_spanning_tree(adj, start_node=0):
    mst = []
    visited = set()
    min_heap = [(0, start_node, -1)]  # (weight, current_node, parent_node)
    
    while min_heap:
        weight, node, parent = heapq.heappop(min_heap)

siavashk

def recursive_eulerian_path(adj, start_node):
    def dfs(start):
        stack = [start]
        path = []
        while stack:
            while temp_adj[stack[-1]]:
                next_node = adj[stack[-1]].pop()
                stack.append(next_node)
            path.append(stack.pop())
        return path[::-1]

siavashk

# graph: node -> [(neighbor_1, weight_1), (neighbor_2, weight_2), ...]
import heapq

def dijkstra(graph, start):
    pq = [(0, start)]
    
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    prev = {node: None for node in graph}

siavashk

from collections import deque
from typing import Dict, List


def topological_sort_dfs(nodes: List[int], edges: Dict[int, List[int]]):
    visited = set()
    stack = []
    on_path = set()  # To detect cycles
    
    def dfs(node):

siavashk

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):

siavashk

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def add(self, x):
        """
        Adds a new element to the Union-Find structure.
        Initializes the element as its own parent (singleton set).
        """

siavashk

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


from collections import deque