Advanced graphs & flows

INF = float("inf")

def floyd_warshall(n, edges):
    """All-pairs shortest paths. edges: list of (u, v, w), directed.
    Returns dist matrix; dist[i][j] = cheapest i->j (INF if unreachable)."""
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)      # keep the cheapest parallel edge
    # k is the "highest intermediate vertex allowed" — grow it one at a time
    for k in range(n):
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:                   # no path i..k, skip the whole row
                continue
            di = dist[i]
            for j in range(n):
                through_k = dik + dk[j]
                if through_k < di[j]:
                    di[j] = through_k
    return dist

def negative_cycle(dist):
    """A negative cycle exists iff some vertex can improve its own 0 distance."""
    return any(dist[i][i] < 0 for i in range(len(dist)))

# 4 nodes; note the cheaper 0->1->2 (=3) beats direct 0->2 (=10)
edges = [(0, 1, 1), (1, 2, 2), (0, 2, 10), (2, 3, 1), (3, 1, 4)]
d = floyd_warshall(4, edges)
print("0->2 :", d[0][2])          # 3, via node 1
print("0->3 :", d[0][3])          # 4
print("negative cycle?", negative_cycle(d))

import heapq

def astar(graph, start, goal, h):
    """A* on a weighted graph. graph: {node: [(nbr, cost), ...]}.
    h(n) = admissible heuristic (never overestimates the true remaining cost).
    Returns (path, cost) or (None, inf)."""
    # frontier holds (f = g + h, g, node); g is the real cost from start
    frontier = [(h(start), 0, start)]
    best_g = {start: 0}
    parent = {start: None}
    while frontier:
        f, g, node = heapq.heappop(frontier)
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1], g
        if g > best_g.get(node, float("inf")):
            continue                          # stale heap entry, skip
        for nbr, cost in graph[node]:
            ng = g + cost
            if ng < best_g.get(nbr, float("inf")):
                best_g[nbr] = ng
                parent[nbr] = node
                heapq.heappush(frontier, (ng + h(nbr), ng, nbr))
    return None, float("inf")

# A 3x3 grid; move cost 1; heuristic = Manhattan distance (admissible on a grid)
def grid_graph(n):
    g = {}
    for r in range(n):
        for c in range(n):
            g[(r, c)] = [((r+dr, c+dc), 1) for dr, dc in ((1,0),(-1,0),(0,1),(0,-1))
                         if 0 <= r+dr < n and 0 <= c+dc < n]
    return g

goal = (2, 2)
manhattan = lambda p: abs(p[0]-goal[0]) + abs(p[1]-goal[1])
path, cost = astar(grid_graph(3), (0, 0), goal, manhattan)
print("path :", path)
print("cost :", cost)             # 4 (Manhattan distance corner to corner)

from collections import defaultdict

def kosaraju(n, adj):
    """Strongly connected components via Kosaraju's two-pass DFS.
    adj: {u: [v, ...]} directed. Returns list of components (lists of nodes)."""
    visited = [False] * n
    order = []                                # finish-time order (post-order)

    def dfs1(u):                              # iterative to dodge recursion limits
        stack = [(u, iter(adj[u]))]
        visited[u] = True
        while stack:
            node, it = stack[-1]
            for v in it:
                if not visited[v]:
                    visited[v] = True
                    stack.append((v, iter(adj[v])))
                    break
            else:
                order.append(node)            # all children done -> record finish
                stack.pop()

    for u in range(n):
        if not visited[u]:
            dfs1(u)

    radj = defaultdict(list)                   # reverse every edge
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)

    comp = [-1] * n
    def dfs2(u, cid):
        stack = [u]
        comp[u] = cid
        while stack:
            node = stack.pop()
            for v in radj[node]:
                if comp[v] == -1:
                    comp[v] = cid
                    stack.append(v)

    cid = 0
    for u in reversed(order):                  # decreasing finish time
        if comp[u] == -1:
            dfs2(u, cid); cid += 1
    groups = defaultdict(list)
    for node, c in enumerate(comp):
        groups[c].append(node)
    return list(groups.values())

# 0->1->2->0 is one cycle (an SCC); 3 hangs off it alone
adj = {0: [1], 1: [2], 2: [0, 3], 3: []}
print(sorted(sorted(c) for c in kosaraju(4, adj)))   # [[0,1,2],[3]]

def tarjan_scc(n, adj):
    """Tarjan's single-pass SCC. Returns list of components.
    index = DFS discovery time; low = lowest index reachable from the subtree."""
    index = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack, comps = [], []
    counter = [0]

    def strongconnect(v):
        # explicit-stack DFS carrying an iterator per frame
        work = [(v, iter(adj[v]))]
        index[v] = low[v] = counter[0]; counter[0] += 1
        stack.append(v); on_stack[v] = True
        while work:
            node, it = work[-1]
            advanced = False
            for w in it:
                if index[w] == -1:
                    index[w] = low[w] = counter[0]; counter[0] += 1
                    stack.append(w); on_stack[w] = True
                    work.append((w, iter(adj[w])))
                    advanced = True
                    break
                elif on_stack[w]:
                    low[node] = min(low[node], index[w])   # back-edge
            if advanced:
                continue
            work.pop()
            if work:                                        # fold child low into parent
                low[work[-1][0]] = min(low[work[-1][0]], low[node])
            if low[node] == index[node]:                    # node is an SCC root
                comp = []
                while True:
                    w = stack.pop(); on_stack[w] = False
                    comp.append(w)
                    if w == node:
                        break
                comps.append(comp)

    for v in range(n):
        if index[v] == -1:
            strongconnect(v)
    return comps

adj = {0: [1], 1: [2], 2: [0, 3], 3: []}
print(sorted(sorted(c) for c in tarjan_scc(4, adj)))   # [[0,1,2],[3]]

from collections import defaultdict, deque

class MaxFlow:
    """Edmonds-Karp: Ford-Fulkerson using BFS to find augmenting paths.
    Runs in O(V * E^2) — polynomial, unlike naive DFS Ford-Fulkerson."""
    def __init__(self, n):
        self.n = n
        self.cap = defaultdict(int)          # (u, v) -> residual capacity
        self.adj = defaultdict(set)          # neighbours in the residual graph

    def add_edge(self, u, v, c):
        self.cap[(u, v)] += c
        self.adj[u].add(v); self.adj[v].add(u)   # reverse edge starts at 0

    def _bfs(self, s, t, parent):
        parent.clear(); parent[s] = s
        q = deque([s])
        while q:
            u = q.popleft()
            for v in self.adj[u]:
                if v not in parent and self.cap[(u, v)] > 0:
                    parent[v] = u
                    if v == t:
                        return True
                    q.append(v)
        return False

    def max_flow(self, s, t):
        flow, parent = 0, {}
        while self._bfs(s, t, parent):
            # bottleneck = smallest residual capacity along the found path
            v, bottleneck = t, float("inf")
            while v != s:
                u = parent[v]
                bottleneck = min(bottleneck, self.cap[(u, v)])
                v = u
            v = t
            while v != s:                    # push flow, add residual back-edge
                u = parent[v]
                self.cap[(u, v)] -= bottleneck
                self.cap[(v, u)] += bottleneck
                v = u
            flow += bottleneck
        return flow

    def min_cut(self, s):
        """After max_flow, vertices reachable from s in the residual graph are
        the source side of a minimum cut (max-flow min-cut theorem)."""
        seen = {s}; q = deque([s])
        while q:
            u = q.popleft()
            for v in self.adj[u]:
                if v not in seen and self.cap[(u, v)] > 0:
                    seen.add(v); q.append(v)
        return seen

mf = MaxFlow(4)
for u, v, c in [(0,1,3),(0,2,2),(1,2,1),(1,3,2),(2,3,3)]:
    mf.add_edge(u, v, c)
print("max flow 0->3 :", mf.max_flow(0, 3))    # 5 (both source edges saturate)
print("source side of min cut :", sorted(mf.min_cut(0)))

def hopcroft_style_matching(left, adj):
    """Maximum bipartite matching via repeated augmenting paths (Hungarian /
    Kuhn's algorithm). left = list of left-side nodes; adj[l] = allowed rights.
    Returns dict right -> left. O(V * E)."""
    match_r = {}                              # right node -> matched left node

    def try_augment(u, seen):
        for v in adj[u]:
            if v in seen:
                continue
            seen.add(v)
            # v is free, or its current partner can be rematched elsewhere
            if v not in match_r or try_augment(match_r[v], seen):
                match_r[v] = u
                return True
        return False

    for u in left:
        try_augment(u, set())
    return match_r

# workers -> tasks they can do; find the largest set of disjoint assignments
adj = {"w1": ["t1", "t2"], "w2": ["t1"], "w3": ["t2", "t3"]}
m = hopcroft_style_matching(["w1", "w2", "w3"], adj)
pairs = sorted((l, r) for r, l in m.items())
print("assignments :", pairs)
print("matching size :", len(m))              # 3 — everyone gets a task

def articulation_and_bridges(n, adj):
    """Find articulation points (cut vertices) and bridges (cut edges) in one
    DFS using discovery times and low-links. Undirected graph. O(V + E)."""
    disc = [-1] * n
    low = [0] * n
    timer = [0]
    aps = set()
    bridges = []

    def dfs(root):
        stack = [(root, -1, iter(adj[root]))]
        disc[root] = low[root] = timer[0]; timer[0] += 1
        child_count = 0                       # children of the DFS root
        while stack:
            u, parent, it = stack[-1]
            for w in it:
                if disc[w] == -1:
                    if parent == -1:
                        child_count += 1
                    disc[w] = low[w] = timer[0]; timer[0] += 1
                    stack.append((w, u, iter(adj[w])))
                    break
                elif w != parent:
                    low[u] = min(low[u], disc[w])   # back-edge
            else:
                stack.pop()
                if stack:
                    pu = stack[-1][0]
                    low[pu] = min(low[pu], low[u])
                    # non-root u's parent is an AP if u can't reach above it
                    if stack[-1][1] != -1 and low[u] >= disc[pu]:
                        aps.add(pu)
                    if low[u] > disc[pu]:           # nothing below reaches pu -> bridge
                        bridges.append(tuple(sorted((pu, u))))
        if child_count > 1:                          # root is an AP iff 2+ children
            aps.add(root)

    for v in range(n):
        if disc[v] == -1:
            dfs(v)
    return sorted(aps), sorted(bridges)

# path 0-1-2 with a triangle 2-3-4-2; node 2 and edge (1,2) are cut points
adj = {0: [1], 1: [0, 2], 2: [1, 3, 4], 3: [2, 4], 4: [2, 3]}
aps, bridges = articulation_and_bridges(5, adj)
print("articulation points :", aps)     # [1, 2]
print("bridges :", bridges)             # [(0, 1), (1, 2)]