Lab 01 — Max Flow (Dinic’s Algorithm)

Goal

Implement Dinic’s algorithm for maximum flow on a directed graph with capacities, achieving O(V²·E) worst case and near-linear in practice. Apply it to a real interview-style problem (Maximum Students Taking Exam, LC 1349) by reducing to max flow / bipartite matching.

Background

Maximum flow is the foundational network flow problem: given a source s and sink t in a directed graph with edge capacities, find the maximum rate at which “flow” can travel from s to t respecting capacities.

Key algorithms:

  • Ford-Fulkerson (1956): generic augmenting-path framework. Complexity depends on path choice.
  • Edmonds-Karp (1972): BFS for shortest augmenting path. O(V·E²).
  • Dinic (1970): level graphs + blocking flows. O(V²·E) general; O(E·√V) for bipartite matching.
  • Push-relabel (Goldberg-Tarjan, 1986): faster in practice for dense graphs. O(V²·√E) with FIFO.

Why Dinic dominates in practice: the level graph constraint (only follow edges from level i to level i+1 in BFS layering) prunes the search dramatically. For random graphs, near-linear.

Interview Context

Max flow is asked in:

  • ICPC regionals/world finals (universal)
  • Quant developer rounds at funds that care about assignment-style problems
  • A handful of Google L6+ research interviews
  • Rare appearances at Snowflake / Databricks query optimizer roles (max-flow underpins some join reordering heuristics)
  • Never in standard FAANG SWE interviews

If asked, expect to either implement Dinic from scratch OR identify that a problem reduces to max flow and explain the reduction (more common than full implementation).

When to Skip This Topic

Skip if any of these are true:

  • You are not interviewing for quant / research / ICPC-adjacent roles
  • You have not memorized the basic Ford-Fulkerson framework yet
  • You have less than 4 weeks for this phase

The reduction skill (recognizing a problem as max flow) is more valuable than memorizing the implementation. If you have only a few days, study reductions and skip the implementation.

Problem Statement

Maximum Students Taking Exam (LeetCode 1349, Hard).

Given an m × n classroom matrix where each cell is either ‘.’ (good seat) or ‘#’ (broken). Place students such that no student can cheat — a student can cheat off any immediately adjacent student in the same row OR diagonally in front (one row earlier, column ±1). Maximize the number of students seated.

seats = [["#",".","#","#",".","#"],
         [".","#","#","#","#","."],
         ["#",".","#","#",".","#"]]
output = 4

Constraints

  • 1 ≤ m, n ≤ 8 (small grid — but max-flow approach generalizes)
  • Up to 64 seats
  • Wall-clock target: < 100ms

Clarifying Questions

  1. Can a student cheat off the seat directly in front (same column, previous row)? (No — only diagonal-front and same-row-adjacent.)
  2. Are broken seats unavailable for sitting? (Yes — ‘#’ cannot hold a student.)
  3. Is the grid always rectangular? (Yes.)

Examples

Example 1

seats = [[".","#","."],
         ["#",".","#"],
         [".","#","."]]

Conflict graph: every ‘.’ conflicts with diagonal-front + same-row-adjacent. Maximum independent set = 4 (the corners).

Example 2

seats = [["."]]

Trivial: 1.

Example 3 (boundary)

seats = [[".",".",".","..."]]   # single row, all good

Same-row-adjacency means max alternating = ⌈n/2⌉.

Brute Force

Try every subset of good seats; check no two are in conflict; track max. O(2^k · k²) where k = number of good seats. For 8×8 = 64, infeasible.

Brute Force Complexity

  • Time: O(2^k · k²) — fails for k > ~20.
  • Space: O(k) for current subset.

Optimization Path

Observation 1: this is maximum independent set on a conflict graph, which is NP-hard in general.

Observation 2: but our conflict graph is bipartite! Color seats by column parity (even/odd columns). All conflicts are between an even column and an odd column (same-row-adjacent: differs by 1; diagonal: also differs by 1). So no conflicts within the even-column set or within the odd-column set.

Observation 3: max independent set on a bipartite graph = total vertices − max matching (König’s theorem). So we compute max bipartite matching, which is solvable in polynomial time via max flow.

This is the canonical reduction trick.

Final Expected Approach

  1. Build the bipartite graph: left = good seats in even columns, right = good seats in odd columns. Edge between two if they conflict.
  2. Add source s → all left nodes (cap 1), all right nodes → sink t (cap 1), all conflict edges left→right (cap 1).
  3. Run Dinic to compute max flow = max matching.
  4. Answer = (total good seats) − (max matching).

Data Structures

  • Adjacency list with edge-index representation (each edge stores to, cap, rev-index for the reverse edge)
  • BFS level array
  • DFS iterator per node (incremented across calls to skip dead branches)
  • Queue for BFS

Correctness Argument

  • Bipartite: any conflict involves columns differing by 1, hence different parities.
  • König: in bipartite, |min vertex cover| = |max matching|; |max independent set| = |V| − |min vertex cover|. So |MIS| = |V| − |max matching|.
  • Dinic correctness: Ford-Fulkerson framework with augmenting paths; terminates when no augmenting path exists; gives optimal flow by max-flow min-cut theorem.
  • Reduction: max matching via max flow is exact when all edge capacities are 1 and source/sink edges all have capacity 1.

Complexity

  • Dinic on bipartite (unit-capacity) graphs: O(E·√V) — the Hopcroft-Karp bound.
  • For LC 1349: V ≤ 64, E ≤ 64 × 4 = 256. Trivial.

Implementation Requirements

class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
    
    def add_edge(self, u, v, cap):
        self.graph[u].append([v, cap, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])
    
    def _bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap, _ in self.graph[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0
    
    def _dfs(self, u, t, pushed):
        if u == t: return pushed
        while self.it[u] < len(self.graph[u]):
            e = self.graph[u][self.it[u]]
            v, cap, rev = e
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self._dfs(v, t, min(pushed, cap))
                if d > 0:
                    e[1] -= d
                    self.graph[v][rev][1] += d
                    return d
            self.it[u] += 1
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while self._bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self._dfs(s, t, float('inf'))
                if f == 0: break
                flow += f
        return flow

Then build the bipartite graph and call.

Tests

  • LC 1349 given examples
  • All ‘#’ grid → 0
  • All ‘.’ grid of size 1×n → ⌈n/2⌉
  • 8×8 all ‘.’ (max stress) → ~32 (need to compute)
  • Single column m×1 all ‘.’ → m (no same-row conflicts within a column)

Follow-up Questions

  • Generalize to weighted matching (different students have different “value”; maximize total value). → Min-cost max flow.
  • Add a constraint that some seats are mandatory. → Force-include via lower-bound constraints.
  • m, n up to 50. → Same algorithm; check timing.
  • Stream of conflicts; dynamic max matching. → Active research area.
  • Distinct from LC 1349, prove the bipartite reduction is tight.

Product Extension

Real systems that use max flow / bipartite matching:

  • Ride-sharing assignment (drivers ↔ requests)
  • Ad auction allocation (advertisers ↔ slots)
  • Resource scheduling (tasks ↔ machines)
  • Compiler register allocation (variables ↔ registers; with constraints)
  • DNA sequencing assembly

Language/Runtime Follow-ups

  • Python: recursion depth limit; switch to iterative DFS for large V.
  • C++: much faster; competitive programmers use this exclusively.
  • Go/Java: stack size for recursive DFS may need explicit increase.

Common Bugs

  1. Forgot the reverse edge. Flow networks require residual graph; no reverse = wrong answer.
  2. Reverse edge with cap 0 but didn’t account for it during DFS: correct — that’s by design.
  3. BFS level updated multiple times. Use the first level reached only.
  4. DFS iterator reset every call to _dfs. Should persist within a phase (the self.it[u] trick).
  5. Bipartite assumption violated: if you add an edge between two left nodes, the reduction breaks. Verify.
  6. Source/sink indices clash with vertex IDs. Use distinct numbering scheme.

Debugging Strategy

  • Print the level graph after each BFS.
  • Print augmenting path found in each DFS.
  • Verify flow conservation at intermediate nodes after termination.
  • Sanity check: max flow ≤ min(deg(s), deg(t)).

Mastery Criteria

  • Implement Dinic from memory in ≤ 25 min in your primary language
  • Identify max-flow reductions in problems that don’t mention “flow” or “matching” explicitly
  • Explain why LC 1349 reduces to bipartite matching, citing König
  • State Hopcroft-Karp’s complexity advantage on bipartite unit-cap graphs
  • Estimate runtime for a given V, E
  • Implement min-cost max flow if asked (separate algorithm — SPFA + Dinic)