⚙️AlgorithmIntermediate

Flow - Modeling Techniques

Key Points

•
Many classic problems can be modeled as a maximum flow problem by building the right network and capacities.
•
Bipartite maximum matching reduces to max flow with unit capacities and a super-source/super-sink.
•
Minimum vertex cover and maximum independent set in bipartite graphs can be recovered from the residual graph after max matching (Kőnig’s theorem).
•
Vertex capacities are enforced by splitting each vertex into an in-node and an out-node connected by a capacity edge.
•
Edge-disjoint s–t paths equal the max flow value in a unit-capacity directed graph (by Menger’s theorem).
•
Use reverse edges and residual capacities to allow flow to reroute during augmentation.
•
For integer capacities, there always exists an integral max flow, which makes combinatorial extraction (paths, matchings) possible.
•
Modeling details (directions, unit capacities, node-splitting) are the difference between correct and wrong answers in contests.

Prerequisites

→Graphs and basic terminology — Understanding vertices, edges, directed vs. undirected graphs is essential for building flow networks.
→BFS and DFS — Level graph construction and path finding in residual graphs rely on BFS/DFS techniques.
→Residual graphs and augmenting paths — Flow algorithms operate on residual capacity; modeling correctness depends on residual reasoning.
→Bipartite graphs — Reductions for matching, vertex cover, and independent set specifically exploit bipartite structure.
→Asymptotic complexity (Big-O) — Analyzing the performance of Dinic and understanding how modeling changes n and m requires Big-O.

Detailed Explanation

Tap terms for definitions

01Overview

Hook: Imagine organizing traffic so that as many cars as possible reach the stadium on time. You control which roads are open and how many cars each road can handle. How do you decide the best routing? Concept: Maximum flow finds the greatest amount of stuff (cars, data, goods) you can push from a source to a sink through a network with limited capacities, by respecting how much each road (edge) can carry. Modeling techniques translate unrelated combinatorial problems—matching teams to judges, picking a minimum set of checkpoints to cover all roads, or finding many edge-disjoint routes—into this single flow framework. Example: Matching applicants to jobs (each applicant can take one job, each job can accept one applicant) becomes a max flow with a super-source to applicants, edges from applicants to acceptable jobs, and jobs to a super-sink; the max flow equals the maximum matching size.

02Intuition & Analogies

Hook: Flow is like water through pipes or traffic on roads. If each pipe has a width (capacity), the total water reaching the tank (sink) is limited by narrow points (bottlenecks). Concept: By turning problems into a network of pipes where choices correspond to opening certain pipes, we can let max flow automatically find the optimal combination. Example 1: Bipartite matching is like pairing dancers from two groups. Connect source to each left dancer (capacity 1), connect compatible pairs (capacity 1), and connect each right dancer to sink (capacity 1). The amount of water that makes it through equals the number of pairs. Example 2: Vertex capacity is like a toll booth that can process only c people per minute. To limit how many pass through this booth, split it into an entrance and exit with a pipe of capacity c in between; all incoming roads must enter the entrance, and all outgoing roads must leave the exit. Example 3: Edge-disjoint paths are like finding as many separate streets from home to school where no street is used twice; put capacity 1 on each street and see how many units of water make it to school. The key modeling trick is to encode constraints as capacities and structure as directed edges so the max flow machinery does the optimization for you.

03Formal Definition

A flow network is a directed graph G = (V, E) with a source s, sink t, and capacities c: E →

R_{\geq 0}

. A flow is a function f: E →

R_{\geq 0}

that satisfies capacity constraints 0

\leq

f(e)

\leq

c(e) for all e

\in

E and flow conservation

\sum_{e \in δ^{+} (v)}

f(e) -

\sum_{e \in δ^{-} (v)}

f(e) = 0 for all v

\in

∖

\{s, t\}. The value of a flow is

∣ f ∣

\sum_{e \in δ^{+} (s)}

f(e) -

\sum_{e \in δ^{-} (s)}

f(e). The residual capacity of edge (u, v) is

c_{f}

(u, v) = c(u, v) - f(u, v) plus a reverse edge (v, u) with capacity f(u, v), forming the residual graph. The Max-Flow Min-Cut Theorem states that the maximum flow value equals the minimum s–t cut capacity, where the cut capacity is c(S, T) =

\sum_{u \in S, v \in T}

c(u, v) for any partition (S, T) of V with s

\in

S and t

\in

T. When all capacities are integers, there exists an integral maximum flow. Reductions: Bipartite matching is modeled by a unit-capacity network with layers

s \to L

→

R \to t

. Vertex capacities are enforced by node splitting: replace v with

v_{in}

and

v_{o u t}

, add edge (

v_{in}

v_{o u t}

) of capacity

c_{v}

, redirect all incoming edges to

v_{in}

and all outgoing edges from

v_{o u t}

04When to Use

Use bipartite matching via max flow when each item on the left can match to at most one on the right (or small fixed numbers), and compatibility is a graph. Examples: job assignment, seating constraints, pairing problems, grid tiling (domino tilings), classroom scheduling. Use vertex-splitting when the limitation is on how many times a vertex can be used, such as throttling servers (node capacity), limiting how many teams pass through a checkpoint, or selecting at most k uses of an object represented by a vertex. Use minimum vertex cover in bipartite graphs when you must pick the smallest set of vertices that touches every L–R edge (e.g., minimum guards covering all corridors between two partitions). Since |MVC| = |MaxMatching|, solve matching and recover the cover from the residual graph. Use maximum independent set in bipartite graphs when you need the largest set of vertices with no edges between them; compute |MIS| = |L| + |R| - |MVC| and extract the set from the same residual traversal. Use edge-disjoint paths when you want as many separate routes as possible with no shared edges; model by unit-capacity edges and run max flow, optionally reconstructing the paths from the integral flow.

⚠️Common Mistakes

Forgetting reverse edges: Max flow needs residual edges with initial capacity 0 so flow can be canceled and rerouted. Without them, your algorithm may get stuck in suboptimal states. - Wrong directions or missing super-source/super-sink: In bipartite matching you must connect s → L, L → R, and R → t with unit capacities. Reversing any layer or missing a layer breaks conservation or allows multi-matching. - Mixing edge and vertex capacities: When the constraint is on vertex usage, splitting is required; putting capacity on incident edges alone does not limit the vertex’s total throughput. - Overflow and types: Capacities can exceed 32-bit int in some problems; use 64-bit (long long) to avoid overflow. - Incorrect min vertex cover extraction: For bipartite graphs after max matching, compute Z = vertices reachable from s in the residual graph using edges with positive residual capacity; the minimum vertex cover is (L \ Z) ∪ (R ∩ Z), not simply the cut from max-flow min-cut. - Unit vs. non-unit capacity in matching: For classic matching, all capacities in L → R and s/t edges must be 1; otherwise you compute b-matching or a different problem. - Path reconstruction pitfalls: To extract edge-disjoint paths, track actual flow on forward edges (flow = orig_cap − residual_cap) and consume one unit per traversal to avoid reusing edges; naive greedy walks can get stuck in cycles if you do not backtrack.

Key Formulas

Flow conservation

e \in δ^{+} (v) \sum f (e) - e \in δ^{-} (v) \sum f (e) = 0 for v \neq = s, t

Explanation: Except at the source and sink, total flow leaving a node equals total flow entering. This enforces that flow doesn't appear or disappear.

Capacity constraint

0 \leq f (e) \leq c (e)

Explanation: Flow on each edge cannot be negative and cannot exceed its capacity. This bounds how much can be sent through an edge.

Value of a flow

∣ f ∣ = e \in δ^{+} (s) \sum f (e) - e \in δ^{-} (s) \sum f (e)

Explanation: The net flow out of the source equals the total amount delivered to the sink. This is what max flow maximizes.

Residual capacity

c_{f} (u, v) = c (u, v) - f (u, v)

Explanation: Residual capacity indicates how much more flow can be pushed along an edge. Reverse edges get capacity f(u, v) to allow canceling earlier decisions.

Max-Flow Min-Cut Theorem

f max ∣ f ∣ = (S, T) min c (S, T), c (S, T) = u \in S, v \in T \sum c (u, v)

Explanation: The best you can route equals the capacity of the narrowest cut separating source and sink. This duality certifies optimality of a max flow.

Node splitting

Split v \to v_{in}, v_{o u t} and add edge (v_{in}, v_{o u t}) with capacity c_{v}

Explanation: To enforce a vertex capacity $c_{v}$ , require every traversal of v to pass through the internal edge $v_{i} n$ → $v_{o} u t$ . This bounds the total flow through v.

Kőnig's theorem (cardinality)

∣ MVC ∣ = ∣ MM ∣

Explanation: In bipartite graphs, the size of a minimum vertex cover equals the size of a maximum matching. This lets us compute MVC via matching (flow).

Bipartite MIS size

∣ MIS ∣ = ∣ L ∣ + ∣ R ∣ - ∣ MVC ∣

Explanation: In any bipartite graph, the maximum independent set size equals total vertices minus the minimum vertex cover size. After getting MVC, MIS size follows immediately.

Edge-disjoint paths count

λ_{e d g e} (s, t) = max ∣ f ∣ in unit-capacity network

Explanation: The maximum number of edge-disjoint s–t paths equals the max flow value when every edge has capacity 1. This is a corollary of Menger's theorem.

Dinic complexity

Dinic: T (n, m) = O (m n^{2}) in general, O (m n) on bipartite/unit networks

Explanation: Dinic's algorithm runs in O(m $n^{2}$ ) in the worst case but is much faster in practice; on unit capacity or bipartite graphs it achieves O(m sqrt(n)).

Augmentation on a path

f^{'} (e) = f (e) + Δ \cdot χ_{P} (e), Δ = e \in P min c_{f} (e)

Explanation: When an augmenting path P exists, increase flow on P by the path's bottleneck capacity Δ. This iteratively builds up the max flow.

Integrality of max flow

\forall e, c (e) \in Z ⟹ \exists f^{*} optimal with f^{*} (e) \in Z

Explanation: If all capacities are integers, there is a maximum flow with integer values. This guarantees combinatorial outputs like exact matchings or disjoint paths.

Complexity Analysis

Let n =

∣ V ∣

and m =

∣ E ∣

in the constructed flow network. Dinic's algorithm runs in O(m

n^{2}

) time in general and O(m sqrt{n}) on bipartite/unit-capacity networks. Space is O(n + m) for storing the layered residual graph. Modeling affects both n and m: node splitting for vertex capacities replaces each original vertex v by

v_{i} n

and

v_{o} u t

and adds one internal edge, so the new network has n' = n +

∣ V ∣

(roughly 2n) vertices and m' = m +

∣ V ∣

edges; asymptotically this keeps complexity linear in the input size. For bipartite matching with L left nodes, R right nodes, and E edges, the network has L + R + 2 vertices and E + L + R edges; with unit capacities Dinic achieves O(E sqrt(L + R)) time and O(E + L + R) space. For edge-disjoint paths in a directed unit-capacity graph, the same O(m sqrt{n}) bound applies, and by integrality the max flow value equals the number of paths. Extracting k edge-disjoint paths from an integral flow can be done in O(k m) worst case by repeatedly DFS-ing along edges with positive flow, but in practice it is O(total edges used by paths). When adding super-source/sink, costs are negligible relative to m. Beware capacity scaling or very large integer capacities: while algorithmic complexity depends on graph structure, numeric overflows can occur if 32-bit ints are used; using 64-bit (long long) protects against capacity sums up to about 9e18. Overall, these reductions preserve polynomial size and allow competitive runtimes up to about 2e5 edges with Dinic in typical contest constraints.

Code Examples

Reusable Dinic max flow implementation (64-bit capacities)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Dinic {
5     struct Edge {
6         int to, rev;
7         long long cap, orig_cap;
8     };
9     int n;
10     vector<vector<Edge>> g;
11     vector<int> level, it;
12     Dinic(int n = 0): n(n), g(n), level(n), it(n) {}
13     void reset(int n_) { n = n_; g.assign(n, {}); level.assign(n, 0); it.assign(n, 0); }
14     void add_edge(int u, int v, long long c) {
15         Edge a{v, (int)g[v].size(), c, c};
16         Edge b{u, (int)g[u].size(), 0, 0};
17         g[u].push_back(a);
18         g[v].push_back(b);
19     }
20     bool bfs(int s, int t) {
21         fill(level.begin(), level.end(), -1);
22         queue<int> q; level[s] = 0; q.push(s);
23         while (!q.empty()) {
24             int u = q.front(); q.pop();
25             for (auto &e : g[u]) if (e.cap > 0 && level[e.to] < 0) {
26                 level[e.to] = level[u] + 1;
27                 q.push(e.to);
28             }
29         }
30         return level[t] >= 0;
31     }
32     long long dfs(int u, int t, long long f) {
33         if (u == t) return f;
34         for (int &i = it[u]; i < (int)g[u].size(); ++i) {
35             Edge &e = g[u][i];
36             if (e.cap > 0 && level[e.to] == level[u] + 1) {
37                 long long pushed = dfs(e.to, t, min(f, e.cap));
38                 if (pushed > 0) {
39                     e.cap -= pushed;
40                     g[e.to][e.rev].cap += pushed;
41                     return pushed;
42                 }
43             }
44         }
45         return 0;
46     }
47     long long max_flow(int s, int t) {
48         long long flow = 0;
49         const long long INF = (1LL<<62);
50         while (bfs(s, t)) {
51             fill(it.begin(), it.end(), 0);
52             while (true) {
53                 long long pushed = dfs(s, t, INF);
54                 if (!pushed) break;
55                 flow += pushed;
56             }
57         }
58         return flow;
59     }
60 };
61 
62 int main() {
63     // Example usage: simple 4-node network
64     // 0 -> 1 (3), 0 -> 2 (2), 1 -> 2 (1), 1 -> 3 (2), 2 -> 3 (4)
65     int n = 4; int s = 0, t = 3;
66     Dinic din(n);
67     din.add_edge(0,1,3);
68     din.add_edge(0,2,2);
69     din.add_edge(1,2,1);
70     din.add_edge(1,3,2);
71     din.add_edge(2,3,4);
72     cout << din.max_flow(s,t) << "\n"; // Expected 5
73     return 0;
74 }
75

This is a standard Dinic implementation with 64-bit capacities. It constructs a level graph via BFS and pushes blocking flows using DFS while respecting residual capacities and reverse edges. The example network demonstrates a typical small flow; the answer equals the min-cut capacity.

Time: O(m n^2) in general; O(m sqrt(n)) on unit-capacity/bipartite graphsSpace: O(n + m)

Bipartite maximum matching + minimum vertex cover + maximum independent set (Kőnig)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Dinic {
5     struct Edge { int to, rev; long long cap, orig_cap; };
6     int n; vector<vector<Edge>> g; vector<int> level, it;
7     Dinic(int n=0): n(n), g(n), level(n), it(n) {}
8     void add_edge(int u, int v, long long c){ Edge a{v,(int)g[v].size(),c,c}; Edge b{u,(int)g[u].size(),0,0}; g[u].push_back(a); g[v].push_back(b);}    
9     bool bfs(int s,int t){ fill(level.begin(), level.end(), -1); queue<int>q; level[s]=0; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(auto &e:g[u]) if(e.cap>0 && level[e.to]<0){ level[e.to]=level[u]+1; q.push(e.to);} } return level[t]>=0; }
10     long long dfs(int u,int t,long long f){ if(u==t) return f; for(int &i=it[u]; i<(int)g[u].size(); ++i){ auto &e=g[u][i]; if(e.cap>0 && level[e.to]==level[u]+1){ long long ret=dfs(e.to,t,min(f,e.cap)); if(ret>0){ e.cap-=ret; g[e.to][e.rev].cap+=ret; return ret; } } } return 0; }
11     long long max_flow(int s,int t){ long long flow=0, INF=(1LL<<62); level.assign(n,0); it.assign(n,0); while(bfs(s,t)){ fill(it.begin(), it.end(), 0); while(true){ long long f=dfs(s,t,INF); if(!f) break; flow+=f; } } return flow; }
12 };
13 
14 int main(){
15     // Build a bipartite graph L={0..L-1}, R={L..L+R-1}
16     int L = 4, R = 4; // example sizes
17     vector<pair<int,int>> edges = { {0,0}, {0,1}, {1,1}, {1,2}, {2,2}, {3,2}, {3,3} }; // (u in L, v in R)
18 
19     int n = L + R + 2; int S = L + R, T = L + R + 1;
20     Dinic din(n);
21     // s->L, capacity 1
22     for(int u=0; u<L; ++u) din.add_edge(S, u, 1);
23     // L->R, capacity 1
24     for(auto [u,v]: edges) din.add_edge(u, L+v, 1);
25     // R->t, capacity 1
26     for(int v=0; v<R; ++v) din.add_edge(L+v, T, 1);
27 
28     long long maxMatching = din.max_flow(S, T);
29     cout << "Max matching size = " << maxMatching << "\n";
30 
31     // Recover minimum vertex cover (L \ Z) U (R ∩ Z)
32     // Z = vertices reachable from S in residual graph with positive residual capacity
33     vector<int> vis(n, 0);
34     queue<int> q; q.push(S); vis[S] = 1;
35     while(!q.empty()){
36         int u = q.front(); q.pop();
37         for(auto &e : din.g[u]) if(e.cap > 0 && !vis[e.to]){
38             vis[e.to] = 1; q.push(e.to);
39         }
40     }
41     vector<int> minCoverL, minCoverR;
42     for(int u=0; u<L; ++u) if(!vis[u]) minCoverL.push_back(u);
43     for(int v=0; v<R; ++v) if(vis[L+v]) minCoverR.push_back(v);
44 
45     cout << "Minimum Vertex Cover (L part): ";
46     for(int x: minCoverL) cout << x << ' '; cout << "\n";
47     cout << "Minimum Vertex Cover (R part): ";
48     for(int x: minCoverR) cout << x << ' '; cout << "\n";
49 
50     // Maximum independent set in bipartite graphs is the complement of MVC
51     vector<int> MISL, MISR;
52     vector<int> inCoverL(L,0), inCoverR(R,0);
53     for(int x: minCoverL) inCoverL[x]=1; for(int x: minCoverR) inCoverR[x]=1;
54     for(int u=0; u<L; ++u) if(!inCoverL[u]) MISL.push_back(u);
55     for(int v=0; v<R; ++v) if(!inCoverR[v]) MISR.push_back(v);
56     cout << "Maximum Independent Set (L part): ";
57     for(int x: MISL) cout << x << ' '; cout << "\n";
58     cout << "Maximum Independent Set (R part): ";
59     for(int x: MISR) cout << x << ' '; cout << "\n";
60 
61     return 0;
62 }
63

We reduce bipartite matching to max flow with unit capacities and extract a minimum vertex cover via the standard residual reachability rule: Z are nodes reachable from S in the residual graph, MVC = (L \ Z) ∪ (R ∩ Z). The maximum independent set is the complement of the MVC in bipartite graphs.

Time: O(E sqrt(V)) with Dinic on unit-capacity bipartite graphsSpace: O(V + E)

Vertex capacities via node splitting

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Dinic {
5     struct Edge { int to, rev; long long cap, orig_cap; };
6     int n; vector<vector<Edge>> g; vector<int> level, it;
7     Dinic(int n=0): n(n), g(n), level(n), it(n) {}
8     void add_edge(int u,int v,long long c){ Edge a{v,(int)g[v].size(),c,c}; Edge b{u,(int)g[u].size(),0,0}; g[u].push_back(a); g[v].push_back(b);}    
9     bool bfs(int s,int t){ fill(level.begin(), level.end(), -1); queue<int>q; level[s]=0; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(auto &e:g[u]) if(e.cap>0 && level[e.to]<0){ level[e.to]=level[u]+1; q.push(e.to);} } return level[t]>=0; }
10     long long dfs(int u,int t,long long f){ if(u==t) return f; for(int &i=it[u]; i<(int)g[u].size(); ++i){ auto &e=g[u][i]; if(e.cap>0 && level[e.to]==level[u]+1){ long long ret=dfs(e.to,t,min(f,e.cap)); if(ret>0){ e.cap-=ret; g[e.to][e.rev].cap+=ret; return ret; } } } return 0; }
11     long long max_flow(int s,int t){ long long flow=0, INF=(1LL<<62); level.assign(n,0); it.assign(n,0); while(bfs(s,t)){ fill(it.begin(), it.end(), 0); while(true){ long long f=dfs(s,t,INF); if(!f) break; flow+=f; } } return flow; }
12 };
13 
14 // Example: limit how much flow passes through vertices 1 and 2
15 int main(){
16     // Original graph: 0 (source) -> 1,2 -> 3 (sink)
17     // Edge capacities: (0->1)=5, (0->2)=5, (1->3)=5, (2->3)=5
18     // Vertex capacities: cap(1)=3, cap(2)=2 (limit total through node)
19     int origN = 4; // nodes 0..3
20     vector<tuple<int,int,long long>> edges = { {0,1,5}, {0,2,5}, {1,3,5}, {2,3,5} };
21     vector<long long> vcap = { (long long)1e18, 3, 2, (long long)1e18 }; // infinite at 0,3
22 
23     // Build split graph: for each v create v_in and v_out
24     auto inId = [&](int v){ return 2*v; };
25     auto outId = [&](int v){ return 2*v+1; };
26     int N = 2*origN; int S = outId(0), T = inId(3); // choose source as 0_out, sink as 3_in
27     Dinic din(N);
28 
29     // Add vertex capacity edges v_in -> v_out with capacity vcap[v]
30     for(int v=0; v<origN; ++v){
31         din.add_edge(inId(v), outId(v), vcap[v]);
32     }
33     // Redirect original edges u->v as u_out -> v_in with given edge capacities
34     for(auto [u,v,c] : edges){
35         din.add_edge(outId(u), inId(v), c);
36     }
37 
38     cout << din.max_flow(S, T) << "\n"; // Expected 3 + 2 = 5 limited by vertex caps
39     return 0;
40 }
41

We enforce vertex capacities by splitting each node v into v_in → v_out with capacity cap(v). Every original edge (u, v) becomes u_out → v_in. The max flow is thereby limited by how much can pass through each vertex, not just through edges.

Time: O(m' n'^2) in general, where n' ≈ 2n and m' ≈ m + nSpace: O(n' + m')

Edge-disjoint s–t paths: compute count and reconstruct paths

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Dinic {
5     struct Edge { int to, rev; long long cap, orig_cap; };
6     int n; vector<vector<Edge>> g; vector<int> level, it;
7     Dinic(int n=0): n(n), g(n), level(n), it(n) {}
8     void add_edge(int u,int v,long long c){ Edge a{v,(int)g[v].size(),c,c}; Edge b{u,(int)g[u].size(),0,0}; g[u].push_back(a); g[v].push_back(b);}    
9     bool bfs(int s,int t){ fill(level.begin(), level.end(), -1); queue<int>q; level[s]=0; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(auto &e:g[u]) if(e.cap>0 && level[e.to]<0){ level[e.to]=level[u]+1; q.push(e.to);} } return level[t]>=0; }
10     long long dfs(int u,int t,long long f){ if(u==t) return f; for(int &i=it[u]; i<(int)g[u].size(); ++i){ auto &e=g[u][i]; if(e.cap>0 && level[e.to]==level[u]+1){ long long ret=dfs(e.to,t,min(f,e.cap)); if(ret>0){ e.cap-=ret; g[e.to][e.rev].cap+=ret; return ret; } } } return 0; }
11     long long max_flow(int s,int t){ long long flow=0, INF=(1LL<<62); level.assign(n,0); it.assign(n,0); while(bfs(s,t)){ fill(it.begin(), it.end(), 0); while(true){ long long f=dfs(s,t,INF); if(!f) break; flow+=f; } } return flow; }
12 };
13 
14 bool dfs_consume(int u, int t, vector<int> &path, vector<vector<int>> &rem, const vector<vector<Dinic::Edge>> &g){
15     if(u == t) return true;
16     for(int i=0; i<(int)g[u].size(); ++i){
17         const auto &e = g[u][i];
18         if(e.orig_cap > 0 && rem[u][i] > 0){
19             // consume one unit of flow and continue
20             rem[u][i]--;
21             path.push_back(e.to);
22             if(dfs_consume(e.to, t, path, rem, g)) return true;
23             // backtrack
24             path.pop_back();
25             rem[u][i]++;
26         }
27     }
28     return false;
29 }
30 
31 int main(){
32     // Construct a directed graph with unit capacities to find edge-disjoint paths
33     // Example: 0->1->3->5, 0->2->4->5, and 0->1->4->5 share some nodes but not edges
34     int n = 6, s = 0, t = 5;
35     Dinic din(n);
36     auto addU = [&](int u,int v){ din.add_edge(u,v,1); };
37     addU(0,1); addU(1,3); addU(3,5);
38     addU(0,2); addU(2,4); addU(4,5);
39     addU(1,4); // extra cross edge enabling alternative routing
40 
41     long long k = din.max_flow(s, t);
42     cout << "Max number of edge-disjoint paths = " << k << "\n";
43 
44     // Prepare rem[u][i] = flow sent on forward edge u->g[u][i].to
45     vector<vector<int>> rem(n);
46     for(int u=0; u<n; ++u){
47         rem[u].assign(din.g[u].size(), 0);
48         for(int i=0; i<(int)din.g[u].size(); ++i){
49             const auto &e = din.g[u][i];
50             long long used = max(0LL, e.orig_cap - e.cap); // flow used on forward edges
51             // For reverse edges, orig_cap = 0, so they contribute 0
52             rem[u][i] = (int)min(used, 1LL); // unit capacities -> 0 or 1
53         }
54     }
55 
56     // Extract k paths by repeatedly DFS-ing and consuming one unit per traversed edge
57     for(int p=0; p<k; ++p){
58         vector<int> path = {s};
59         bool ok = dfs_consume(s, t, path, rem, din.g);
60         if(!ok){ cerr << "Path reconstruction failed\n"; return 0; }
61         cout << "Path " << (p+1) << ": ";
62         for(size_t i=0;i<path.size();++i){ cout << path[i] << (i+1==path.size()? '\n' : ' '); }
63     }
64     return 0;
65 }
66

Unit capacities guarantee an integral max flow that decomposes into edge-disjoint paths and cycles. We compute max flow, then repeatedly DFS along forward edges with positive flow to extract s–t paths, consuming one unit of flow on each edge during traversal. This yields exactly k edge-disjoint paths.

Time: O(m sqrt(n)) for max flow; O(k m) worst-case for path extractionSpace: O(n + m)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Dinic {
5	struct Edge {
6	int to, rev;
7	long long cap, orig_cap;
8	};
9	int n;
10	vector<vector<Edge>> g;
11	vector<int> level, it;
12	Dinic(int n = 0): n(n), g(n), level(n), it(n) {}
13	void reset(int n_) { n = n_; g.assign(n, {}); level.assign(n, 0); it.assign(n, 0); }
14	void add_edge(int u, int v, long long c) {
15	Edge a{v, (int)g[v].size(), c, c};
16	Edge b{u, (int)g[u].size(), 0, 0};
17	g[u].push_back(a);
18	g[v].push_back(b);
19	}
20	bool bfs(int s, int t) {
21	fill(level.begin(), level.end(), -1);
22	queue<int> q; level[s] = 0; q.push(s);
23	while (!q.empty()) {
24	int u = q.front(); q.pop();
25	for (auto &e : g[u]) if (e.cap > 0 && level[e.to] < 0) {
26	level[e.to] = level[u] + 1;
27	q.push(e.to);
28	}
29	}
30	return level[t] >= 0;
31	}
32	long long dfs(int u, int t, long long f) {
33	if (u == t) return f;
34	for (int &i = it[u]; i < (int)g[u].size(); ++i) {
35	Edge &e = g[u][i];
36	if (e.cap > 0 && level[e.to] == level[u] + 1) {
37	long long pushed = dfs(e.to, t, min(f, e.cap));
38	if (pushed > 0) {
39	e.cap -= pushed;
40	g[e.to][e.rev].cap += pushed;
41	return pushed;
42	}
43	}
44	}
45	return 0;
46	}
47	long long max_flow(int s, int t) {
48	long long flow = 0;
49	const long long INF = (1LL<<62);
50	while (bfs(s, t)) {
51	fill(it.begin(), it.end(), 0);
52	while (true) {
53	long long pushed = dfs(s, t, INF);
54	if (!pushed) break;
55	flow += pushed;
56	}
57	}
58	return flow;
59	}
60	};
61
62	int main() {
63	// Example usage: simple 4-node network
64	// 0 -> 1 (3), 0 -> 2 (2), 1 -> 2 (1), 1 -> 3 (2), 2 -> 3 (4)
65	int n = 4; int s = 0, t = 3;
66	Dinic din(n);
67	din.add_edge(0,1,3);
68	din.add_edge(0,2,2);
69	din.add_edge(1,2,1);
70	din.add_edge(1,3,2);
71	din.add_edge(2,3,4);
72	cout << din.max_flow(s,t) << "\n"; // Expected 5
73	return 0;
74	}
75