ii. Push-Relabel

Instead of augmenting paths, maintain a preflow (vertices may hold excess) and heights $h$ with $h(u)\le h(v)+1$ for every residual edge $(u,v)$. Repeatedly push excess along admissible edges ($h(u)=h(v)+1$) or relabel a vertex with excess but no admissible edge. With highest-label selection and the gap heuristic it runs in $O(V^2\sqrt{E})$ and is often the fastest max-flow in practice on dense or adversarial graphs. Use it when Dinic times out; otherwise Dinic is simpler (Max Flow).

struct PushRelabel {                                         // highest label + gap heuristic
    struct E { int to, rev; ll c; };
    vector<vector<E>> g; vector<ll> ex; vector<int> H, cur; vector<vector<int>> hs;
    PushRelabel(int n) : g(n), ex(n), H(n), cur(n), hs(2 * n) {}
    void addEdge(int s, int t, ll cap, ll rcap = 0) {
        if (s == t) return;
        g[s].push_back({t, sz(g[t]), cap}); g[t].push_back({s, sz(g[s]) - 1, rcap});
    }
    void addFlow(E& e, ll f) {
        E& b = g[e.to][e.rev];
        if (!ex[e.to] && f) hs[H[e.to]].push_back(e.to);
        e.c -= f; ex[e.to] += f; b.c += f; ex[b.to] -= f;
    }
    ll maxflow(int s, int t) {
        int v = sz(g); H[s] = v; ex[t] = 1;                  // ex[t] = 1 keeps t out of the active lists
        vector<int> co(2 * v); co[0] = v - 1;
        for (auto& e : g[s]) addFlow(e, e.c);
        for (int hi = 0;;) {
            while (hs[hi].empty()) if (!hi--) return -ex[s];
            int u = hs[hi].back(); hs[hi].pop_back();
            while (ex[u] > 0) {                               // discharge u
                if (cur[u] == sz(g[u])) {                     // relabel
                    H[u] = 1e9;
                    for (int i = 0; i < sz(g[u]); i++) { auto& e = g[u][i]; if (e.c && H[u] > H[e.to] + 1) H[u] = H[e.to] + 1, cur[u] = i; }
                    if (++co[H[u]], !--co[hi] && hi < v)     // gap: nobody left at height hi
                        for (int i = 0; i < v; i++) if (hi < H[i] && H[i] < v) --co[H[i]], H[i] = v + 1;
                    hi = H[u];
                } else if (g[u][cur[u]].c && H[u] == H[g[u][cur[u]].to] + 1) addFlow(g[u][cur[u]], min(ex[u], g[u][cur[u]].c));
                else ++cur[u];
            }
        }
    }
    bool sourceSide(int a) const { return H[a] >= sz(g); }   // after maxflow: S side of a minimum cut
};

Proof: correctness and the $O(V^{2}E)$ generic bound

Invariant: for every residual edge $(u,v)$, $h(u)\le h(v)+1$. Saturating the source edges at the start respects it because $h(s)=V$ and those edges have no residual left. A push along $(u,v)$ with $h(u)=h(v)+1$ can create the residual edge $(v,u)$, which satisfies $h(v)=h(u)-1\le h(u)+1$. A relabel sets $h(u)=1+\min h(v)$ over residual edges, restoring the invariant at $u$. Termination with a max flow: when no vertex except $s,t$ has excess, the preflow is a flow. If there were an augmenting path $s⇝t$ in the residual graph, it would have at most $V-1$ edges with heights dropping at most 1 per edge, from $h(s)=V$ to $h(t)=0$: impossible. So no augmenting path exists and the flow is maximum. Bounds: a vertex with excess has a residual path back to $s$ (its excess came from $s$), so $h(u)\le h(s)+V-1=2V-1$: at most $O(V^2)$ relabels. Each edge is saturated by a push $O(V)$ times between relabels of its endpoints, $O(VE)$ saturating pushes; non-saturating pushes are bounded by a potential argument ($\sum$ heights of active vertices) by $O(V^{2}E)$. FIFO selection gives $O(V^3)$ and highest-label $O(V^2\sqrt{E})$ by sharper potential arguments.

Gap heuristic: if no vertex has height $k$ (with $k<V$), every vertex above $k$ can no longer reach $t$ (heights drop by at most one per edge), so lift them all to $V+1$ at once; their excess will flow back to $s$. Together with highest-label selection this is the practical speedup. The minimum cut is read from heights: vertices with $h\ge V$ cannot reach $t$.

When it matters: dense graphs with $V\approx 10^3$–$10^4$ and $E\approx 10^6$, unit-capacity graphs with bad structure for Dinic, and problems with many max-flow calls on the same graph (Gomory–Hu).