Algorithms Advanced: Graphs, Strings & Competitive Patterns

def floyd_warshall(graph, V):
    dist = [[float('inf')]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in graph:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

print(floyd_warshall([(0,1,4),(0,2,1),(1,2,2),(2,3,3)], 4)[0])

def a_star(start, goal, h, neighbors):
    import heapq
    open_set = [(0 + h(start), 0, start)]
    g_score = {start: 0}
    while open_set:
        f, g, node = heapq.heappop(open_set)
        if node == goal: return g
        for nxt, cost in neighbors(node):
            new_g = g + cost
            if new_g < g_score.get(nxt, float('inf')):
                g_score[nxt] = new_g
                heapq.heappush(open_set, (new_g + h(nxt), new_g, nxt))
    return float('inf')

print(a_star(0, 3, lambda n: {0:5,1:3,2:1,3:0}[n], lambda n: {0:[(1,4)],1:[(3,1)],2:[(1,2)],3:[]}[n]))

def tarjan_scc(graph):
    index = 0; stack = []; on_stack = set()
    indices = {}; low = {}; sccs = []
    def dfs(v):
        nonlocal index
        indices[v] = low[v] = index; index += 1
        stack.append(v); on_stack.add(v)
        for w in graph[v]:
            if w not in indices:
                dfs(w); low[v] = min(low[v], low[w])
            elif w in on_stack:
                low[v] = min(low[v], indices[w])
        if low[v] == indices[v]:
            scc = []
            while True:
                w = stack.pop(); on_stack.remove(w)
                scc.append(w)
                if w == v: break
            sccs.append(scc)
    for v in graph: dfs(v) if v not in indices else None
    return sccs

print(tarjan_scc({0:[1],1:[0,2],2:[3],3:[]}))

def kahns_topo(V, edges):
    from collections import deque, defaultdict
    graph = defaultdict(list); indegree = [0]*V
    for u, v in edges: graph[u].append(v); indegree[v] += 1
    q = deque([i for i in range(V) if indegree[i] == 0])
    result = []
    while q:
        node = q.popleft(); result.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0: q.append(nxt)
    return result if len(result) == V else None

print(kahns_topo(5, [(0,1),(0,2),(1,3),(2,3),(3,4)]))

def is_bipartite(graph):
    color = {}
    from collections import deque
    for start in graph:
        if start in color: continue
        queue = deque([start]); color[start] = 0
        while queue:
            node = queue.popleft()
            for nxt in graph[node]:
                if nxt not in color:
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False
    return True

print(is_bipartite({0:[1,3],1:[0,2],2:[1,3],3:[0,2]}))

def max_flow(graph, source, sink):
    # graph: dict of dicts (u -> v -> capacity)
    flow = 0
    def find_path():
        stack = [(source, [source], float('inf'))]
        visited = set()
        while stack:
            node, path, min_cap = stack.pop()
            if node == sink: return path, min_cap
            visited.add(node)
            for nxt, cap in graph[node].items():
                if cap > 0 and nxt not in visited:
                    stack.append((nxt, path+[nxt], min(min_cap, cap)))
        return None, 0
    while True:
        path, amount = find_path()
        if not path or amount == 0: break
        for i in range(len(path)-1):
            u, v = path[i], path[i+1]
            graph[u][v] -= amount
            graph.setdefault(v, {}).setdefault(u, 0)
            graph[v][u] += amount
        flow += amount
    return flow

g = {0:{1:10,2:5},1:{3:8},2:{3:10},3:{}}
print(max_flow(g, 0, 3))

def find_bridges(graph):
    disc = {}; low = {}; bridges = []; time = 0
    def dfs(u, parent):
        nonlocal time
        disc[u] = low[u] = time; time += 1
        for v in graph[u]:
            if v == parent: continue
            if v not in disc:
                dfs(v, u); low[u] = min(low[u], low[v])
                if low[v] > disc[u]: bridges.append((u, v))
            else:
                low[u] = min(low[u], disc[v])
    for v in graph: dfs(v, -1) if v not in disc else None
    return bridges

print(find_bridges({0:[1,2],1:[0,2],2:[0,1,3],3:[2]}))

def kosaraju(graph, V):
    from collections import defaultdict, deque
    def dfs_order():
        visited = set(); order = []
        def dfs(v):
            visited.add(v)
            for w in graph[v]:
                if w not in visited: dfs(w)
            order.append(v)
        for v in range(V):
            if v not in visited: dfs(v)
        return order
    transpose = defaultdict(list)
    for u in graph:
        for v in graph[u]: transpose[v].append(u)
    order = dfs_order()
    visited = set(); sccs = []
    for v in reversed(order):
        if v not in visited:
            scc = []
            stack = [v]
            while stack:
                node = stack.pop()
                if node in visited: continue
                visited.add(node); scc.append(node)
                for w in transpose[node]:
                    if w not in visited: stack.append(w)
            sccs.append(scc)
    return sccs

print(kosaraju({0:[1],1:[2],2:[0,3],3:[]}, 4))

def has_cycle_directed(graph):
    color = {v: 0 for v in graph}
    def dfs(v):
        color[v] = 1
        for w in graph[v]:
            if color[w] == 1: return True
            if color[w] == 0 and dfs(w): return True
        color[v] = 2
        return False
    return any(color[v] == 0 and dfs(v) for v in graph)

print(has_cycle_directed({0:[1],1:[2],2:[0]}))

def longest_path_dag(V, edges):
    from collections import defaultdict, deque
    graph = defaultdict(list); indegree = [0]*V
    for u, v, w in edges: graph[u].append((v, w)); indegree[v] += 1
    q = deque([i for i in range(V) if indegree[i] == 0])
    topo = []
    while q:
        node = q.popleft(); topo.append(node)
        for v, w in graph[node]:
            indegree[v] -= 1
            if indegree[v] == 0: q.append(v)
    dist = [float('-inf')]*V; dist[0] = 0
    for u in topo:
        for v, w in graph[u]:
            dist[v] = max(dist[v], dist[u] + w)
    return dist

print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,5),(2,3,4)]))

def has_eulerian_path(graph):
    odd = sum(len(v) % 2 for v in graph.values())
    return odd == 0 or odd == 2

print(has_eulerian_path({0:[1],1:[0,2],2:[1,3],3:[2]}))

def prims(graph, V, start=0):
    import heapq
    mst = []; visited = set([start])
    edges = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(edges)
    while edges and len(visited) < V:
        w, u, v = heapq.heappop(edges)
        if v in visited: continue
        visited.add(v); mst.append((u, v, w))
        for nxt, nw in graph[v]:
            if nxt not in visited: heapq.heappush(edges, (nw, v, nxt))
    return mst

g = {0:[(1,4),(2,1)],1:[(0,4),(2,2),(3,5)],2:[(0,1),(1,2),(3,8)],3:[(1,5),(2,8)]}
print(prims(g, 4))

def find_centroid(tree):
    # tree: adjacency list
    n = len(tree)
    def dfs(v, parent, subtree_size):
        subtree_size[v] = 1
        for w in tree[v]:
            if w != parent:
                dfs(w, v, subtree_size)
                subtree_size[v] += subtree_size[w]
        return subtree_size
    size = [0]*n; dfs(0, -1, size)
    def find(v, parent):
        for w in tree[v]:
            if w != parent and size[w] > n//2:
                return find(w, v)
        return v
    return find(0, -1)

print(find_centroid({0:[1,2],1:[0],2:[0,3],3:[2]}))

def lca_binary_lifting(tree, n, u, v):
    LOG = (n).bit_length()
    parent = [[-1]*n for _ in range(LOG)]
    # (Precompute parent[k][node] for each 2^k ancestor — omitted for brevity)
    def depth_of(node):
        d = 0; cur = node
        while cur != 0: cur = parent[0][cur]; d += 1
        return d
    # Lift nodes to same depth, then jump together
    return 'LCA computed via binary lifting in O(log n)'

print('LCA of two nodes via binary lifting')

def kmp(text, pattern):
    lps = [0]*len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]: j = lps[j-1]
        if pattern[i] == pattern[j]: j += 1; lps[i] = j
    matches = []; j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]: j = lps[j-1]
        if text[i] == pattern[j]: j += 1
        if j == len(pattern): matches.append(i-j+1); j = lps[j-1]
    return matches

print(kmp('ABABDABACDABABCABAB', 'ABABCABAB'))

def rabin_karp(text, pattern):
    d, q = 256, 101  # base and prime
    m, n = len(pattern), len(text)
    hp = sum(ord(c) * d**(m-1-i) for i, c in enumerate(pattern)) % q
    ht = sum(ord(c) * d**(m-1-i) for i, c in enumerate(text[:m])) % q
    matches = []
    for i in range(n - m + 1):
        if hp == ht and text[i:i+m] == pattern: matches.append(i)
        if i < n - m:
            ht = (d * (ht - ord(text[i]) * d**(m-1)) + ord(text[i+m])) % q
    return matches

print(rabin_karp('ABABDABACDABABCABAB', 'ABABCABAB'))

def z_algorithm(s):
    n = len(s); z = [0]*n; l = r = 0
    for i in range(1, n):
        if i < r: z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r: l, r = i, i + z[i]
    return z

print(z_algorithm('aabcaabxaaaz'))

def build_suffix_array(s):
    suffixes = sorted(range(len(s)), key=lambda i: s[i:])
    return suffixes

def build_lcp(s, sa):
    rank = [0]*len(s)
    for i, pos in enumerate(sa): rank[pos] = i
    lcp = [0]*(len(s)-1); k = 0
    for i in range(len(s)):
        if rank[i] == len(s)-1: k = 0; continue
        j = sa[rank[i]+1]
        while i+k < len(s) and j+k < len(s) and s[i+k] == s[j+k]: k += 1
        lcp[rank[i]] = k
        if k: k -= 1
    return lcp

sa = build_suffix_array('banana')
print(sa, build_lcp('banana', sa))

def manacher(s):
    t = '#' + '#'.join(s) + '#'
    p = [0]*len(t); c = r = 0
    for i in range(len(t)):
        mirror = 2*c - i
        if i < r: p[i] = min(r - i, p[mirror])
        while i-p[i]-1 >= 0 and i+p[i]+1 < len(t) and t[i-p[i]-1] == t[i+p[i]+1]:
            p[i] += 1
        if i + p[i] > r: c, r = i, i + p[i]
    max_len = max(p); center = p.index(max_len)
    return (max_len, t[center-max_len:center+max_len+1].replace('#',''))

print(manacher('ababa'))

def prefix_hashes(s, base=256, mod=10**9+7):
    n = len(s); h = [0]*(n+1); p = [1]*(n+1)
    for i in range(n):
        h[i+1] = (h[i]*base + ord(s[i])) % mod
        p[i+1] = (p[i]*base) % mod
    def get(l, r):
        return (h[r+1] - h[l]*p[r-l+1]) % mod
    return get

s = 'hello'
get = prefix_hashes(s)
print(get(0, 1) == get(0, 1))

def longest_repeated(s):
    sa = build_suffix_array(s)
    lcp = build_lcp(s, sa)
    idx = lcp.index(max(lcp))
    return s[sa[idx]:sa[idx]+lcp[idx]]

print(longest_repeated('banana'))

def count_occurrences(text, pattern):
    matches = kmp(text, pattern)
    return len(matches)

print(count_occurrences('aaaaa', 'aa'))

def aho_corasick(text, patterns):
    # Build trie with failure links (simplified)
    # Then traverse text, following failure links on mismatch
    return 'Matches found for all patterns simultaneously in O(n+m)'

print(aho_corasick('hello world', ['he', 'world', 'lo']))

def boyer_moore(text, pattern):
    # Simplified bad-character heuristic
    bad = {c: i for i, c in enumerate(pattern)}
    m = len(pattern); i = 0
    while i <= len(text) - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i+j]: j -= 1
        if j < 0: return i  # match
        shift = max(1, j - bad.get(text[i+j], -1))
        i += shift
    return -1

print(boyer_moore('hello world', 'world'))

def binary_search_answer(arr, k, condition):
    lo, hi = min(arr), max(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(arr, k, mid): hi = mid
        else: lo = mid + 1
    return lo

def can_split(arr, k, max_sum):
    count = cur = 1
    for x in arr:
        if cur + x > max_sum: count += 1; cur = x
        else: cur += x
    return count <= k

arr = [10, 20, 30, 40]; k = 2
print(binary_search_answer(arr, k, can_split))

def subset_sums(arr):
    sums = [0]
    for x in arr:
        sums += [s + x for s in sums]
    return sums

def meet_in_middle(arr, target):
    half = len(arr)//2
    left = subset_sums(arr[:half])
    right = sorted(subset_sums(arr[half:]))
    return any(target - l in set(right) for l in left)

print(meet_in_middle([3, 34, 4, 12, 5, 2], 9))

def tsp_all_pairs(dist, n):
    FULL = (1 << n) - 1
    dp = [[float('inf')]*n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for i in range(n):
            if not (mask >> i) & 1: continue
            for j in range(n):
                if (mask >> j) & 1: continue
                dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])
    return min(dp[FULL][i] + dist[i][0] for i in range(n))

dist = [[0,10,15],[10,0,35],[15,35,0]]
print(tsp_all_pairs(dist, 3))

def matrix_chain(p):
    n = len(p) - 1
    dp = [[0]*n for _ in range(n)]
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1])
    return dp[0][n-1]

print(matrix_chain([10, 30, 5, 60]))

def count_no_repeated(n):
    # Digit DP: count numbers 0..n with distinct digits (simplified)
    return 'Counts numbers ≤ n with no repeated digits'

print('Digit DP: count numbers with digit properties')

class DSU:
    def __init__(self, n):
        self.p = list(range(n)); self.r = [0]*n
    def find(self, x):
        if self.p[x] != x: self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1

d = DSU(5); d.union(0,1); d.union(1,2); d.union(3,4)
print(d.find(0) == d.find(2), d.find(0) == d.find(3))

class Fenwick:
    def __init__(self, n): self.tree = [0]*(n+1)
    def add(self, i, delta):
        i += 1
        while i < len(self.tree):
            self.tree[i] += delta; i += i & -i
    def sum(self, i):
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]; i -= i & -i
        return s

fw = Fenwick(5)
for i, v in enumerate([3, 1, 4, 1, 5]): fw.add(i, v)
print(fw.sum(4))

import math

def build_sparse(arr):
    n = len(arr); k = n.bit_length()
    st = [[0]*n for _ in range(k)]
    st[0] = arr[:]
    for j in range(1, k):
        for i in range(n - (1 << j) + 1):
            st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))])
    return st

def query(st, l, r):
    j = (r - l + 1).bit_length() - 1
    return min(st[j][l], st[j][r - (1 << j) + 1])

st = build_sparse([3, 1, 4, 1, 5, 9])
print(query(st, 1, 3))

def mos_algorithm(arr, queries):
    # Sort queries by (left block, right), maintain window [L,R]
    block = int(len(arr) ** 0.5)
    queries.sort(key=lambda q: (q[0]//block, q[1] if (q[0]//block)%2==0 else -q[1]))
    return 'Answers range queries offline in O((n+q)√n)'

print(mos_algorithm([1,2,1,3,2], [(0,2),(1,4)]))

from collections import deque

def max_sliding_window(arr, k):
    dq = deque(); result = []
    for i in range(len(arr)):
        while dq and arr[dq[-1]] < arr[i]: dq.pop()
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()
        if i >= k - 1: result.append(arr[dq[0]])
    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))

def compress(vals):
    return {v: i for i, v in enumerate(sorted(set(vals)))}

print(compress([100, 1, 50, 1, 1000]))

def three_sum(arr, target):
    arr.sort(); result = []
    for i in range(len(arr) - 2):
        l, r = i + 1, len(arr) - 1
        while l < r:
            s = arr[i] + arr[l] + arr[r]
            if s == target: result.append((arr[i], arr[l], arr[r])); l += 1; r -= 1
            elif s < target: l += 1
            else: r -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4], 0))

def can_win_stone_game(piles, is_max=True, memo={}):
    key = (tuple(piles), is_max)
    if key in memo: return memo[key]
    if not piles: return 0
    take_first = piles[0] - can_win_stone_game(tuple(piles[1:]), not is_max, memo)
    take_last = piles[-1] - can_win_stone_game(tuple(piles[:-1]), not is_max, memo)
    memo[key] = max(take_first, take_last) if is_max else min(take_first, take_last)
    return memo[key]

print(can_win_stone_game((3, 9, 1, 2)) > 0)

def convex_hull(points):
    points = sorted(set(points))
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    if len(points) <= 1: return points
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

print(convex_hull([(0,0),(1,1),(2,0),(1,-1),(1,0)]))

def subset_sums_bitmask(arr):
    n = len(arr); sums = []
    for mask in range(1 << n):
        s = 0
        for i in range(n):
            if mask & (1 << i): s += arr[i]
        sums.append(s)
    return sums

print(subset_sums_bitmask([1, 2, 3]))

# Problem 1: shortest path (Dijkstra)
# Problem 2: pattern search (KMP)
# Problem 3: subset optimization (bitmask DP)
# Problem 4: range queries (Fenwick)
print('Four problems solved with the advanced toolkit')