Max-Flow Augmenting Path Count

Problem

Count how many augmenting paths Ford-Fulkerson pushes before no s-t path remains.

Use DFS over the residual capacity matrix, push the bottleneck along each found path, and increment a counter once per augmentation. edges is a list of directed [u, v, capacity] triples with integer capacities. Return the number of augmentations.

Hint

The path count depends on the traversal order, so scan neighbors in a fixed direction.

Test cases

case 1

in: [4,[[0,1,3],[0,2,2],[1,2,5],[1,3,2],[2,3,3]],0,3]

expected: 3

case 2

in: [3,[[0,1,1],[1,2,1]],0,2]

expected: 1

case 3

in: [3,[[0,1,5]],0,2]

expected: 0

case 4

in: [4,[[0,1,10],[0,2,10],[1,2,1],[1,3,10],[2,3,10]],0,3]

expected: 2

case 5

in: [2,[[0,1,7],[1,0,3]],0,1]

expected: 1

Starter codePython

def max_flow_augmenting_paths(n, edges, s, t):
    # Your code here
    pass

5 test cases · run your code against them in the editor