Level Graphs, Blocking Flows & Why ptr[u] Is Non-Negotiable
Each phase of Dinic's algorithm consists of two steps:
- BFS Level Graph Construction ($O(E)$): Compute unweighted distances $\text{level}[u] = \delta_f(s, u)$ in $G_f$. If $\text{level}[t] = -1$, terminate. Define the level graph $G_L$ containing only residual edges $(u, v)$ with $c_f(u, v) > 0$ and $\text{level}[v] = \text{level}[u] + 1$.
- DFS Blocking Flow with Current-Arc Pruning ($O(V E)$): Repeatedly push augmenting paths from $s$ to $t$ in $G_L$ until no $s \leadsto t$ path remains in $G_L$ (a blocking flow).
Theorem 1 (Strict Increase of $\text{level}[t]$): After a blocking flow saturates $G_L$, no path of length $\text{level}[t]$ remains in $G_f$, and any newly created reverse edges go backward from level $d+1$ to $d$. Thus in the next BFS phase, $\text{level}'[t] \ge \text{level}[t] + 1$. Consequently, there are at most $V - 1$ phases.
Theorem 2 (Role of Current-Arc Pointer int& cid = ptr[u]): During the DFS phase on the DAG $G_L$, each vertex $u$ maintains an index ptr[u] into adj[u]. Whenever dfs(v, ...) returns $0$ (dead end) or saturates edge (u, v), ptr[u] increments. Because $G_L$ only allows forward level edges, no dead-end edge can become viable again until the next BFS phase! Thus:
• Across all DFS calls in one phase, ptr[u] advances at most $\text{deg}(u)$ times, costing $O(E)$ total dead-end work.
• Each successful augmentation takes $O(V)$ steps and saturates at least one edge ($\le E$ times), costing $O(V E)$ per phase and $O(V^2 E)$ total.
Unit Networks & Even-Tarjan $O(E \sqrt{V})$ Theorem
A unit network has integer capacities where every edge has $c(e) = 1$, and every vertex $v \in V \setminus \{s, t\}$ has either in-degree $\le 1$ or out-degree $\le 1$ (which includes all bipartite matching networks). After $\sqrt{V}$ phases of Dinic's algorithm, $\text{level}[t] \ge \sqrt{V}$. Because the residual network can be decomposed into vertex-disjoint augmenting paths, each of length $\ge \sqrt{V}$, at most $V / \sqrt{V} = \sqrt{V}$ additional flow units (and phases) can exist! And because each edge in a unit network is traversed at most once per phase ($O(E)$ per phase), Dinic's algorithm runs in $O(E \sqrt{V})$ time!
Visualize Dinic’s BFS level graph L_G and current-arc DFS blocking flows alongside backward residual arcs (v→u), extract the saturated S-T minimum cut, or step through Hopcroft-Karp disjoint shortest augmenting paths.
Invariant & State
Instead of returning from $t$ all the way back to $s$ after pushing a single bottleneck, production Dinic implementations pass pushed up the recursion stack and continue the loop at node $u$ (flowIn - totalPushedFromU) to saturate multiple branches in a single DFS call, cutting recursion overhead by $3\times$–$5\times$.
| Network Class | Phases | Cost per Phase | Total Time Complexity |
|---|---|---|---|
| General Network | $\le V - 1$ | $O(V E)$ | $O(V^2 E)$ |
| Unit Capacities ($c(e) = 1$) | $O(\min(V^{2/3}, E^{1/2}))$ | $O(E)$ | $O(E \min(V^{2/3}, E^{1/2}))$ |
| Unit Network / Bipartite Matching | $\le 2\sqrt{V}$ | $O(E)$ | $O(E \sqrt{V})$ |
Production C++20 Implementation: Dinic's Algorithm with Multi-Branch Blocking DFS
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
class Dinic {
public:
struct Arc {
int to;
long long cap;
};
explicit Dinic(int n) : numVertices(n), adj(n), level(n), ptr(n) {}
void addEdge(int u, int v, long long cap) {
adj[u].push_back(static_cast<int>(arcs.size()));
arcs.push_back({v, cap});
adj[v].push_back(static_cast<int>(arcs.size()));
arcs.push_back({u, 0});
}
long long maxFlow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
std::fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, t, std::numeric_limits<long long>::max())) {
flow += pushed;
}
}
return flow;
}
private:
int numVertices;
std::vector<Arc> arcs;
std::vector<std::vector<int>> adj;
std::vector<int> level, ptr;
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
std::queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int id : adj[u]) {
int v = arcs[id].to;
if (arcs[id].cap > 0 && level[v] == -1) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[t] != -1;
}
long long dfs(int u, int t, long long available) {
if (available == 0 || u == t) return available;
long long totalPushed = 0;
for (int& cid = ptr[u]; cid < static_cast<int>(adj[u].size()); ++cid) {
int id = adj[u][cid];
int v = arcs[id].to;
if (level[v] != level[u] + 1 || arcs[id].cap == 0) continue;
long long tr = dfs(v, t, std::min(available - totalPushed, arcs[id].cap));
if (tr == 0) continue;
arcs[id].cap -= tr;
arcs[id ^ 1].cap += tr;
totalPushed += tr;
if (totalPushed == available) return totalPushed; // Node u's incoming budget exhausted; do NOT increment cid yet!
}
return totalPushed;
}
};int& cid = ptr[u] (Exponential TLE)If you write for (int cid = 0; cid < adj[u].size(); ++cid) instead of binding a reference int& cid = ptr[u] (or if you increment cid before returning when totalPushed == available while arcs[id].cap > 0), the DFS loses its dead-end memory and re-explores blocked subgraphs in $O(2^V)$ exponential time! Conversely, only advance cid past edge id when arcs[id] is either saturated or leads to a dead end (tr == 0).