Augmenting Path Matching Step

Problem

Perform one Kuhn augmenting step on a bipartite graph.

adj[i] lists the right-side nodes adjacent to left node i. match_left[i] and match_right[j] hold the current matching, or -1 when unmatched. Find the smallest-index unmatched left node and try to augment from it, rerouting earlier matches with DFS. Return the updated match_left list; if nothing changes, return it unchanged.

Hint

A DFS that can reroute the current owner of a right node extends the matching.

Test cases

case 1

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

expected: [0,-1]

case 2

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

expected: [0,-1]

case 3

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

expected: [1,0,-1]

case 4

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

expected: [0,1]

Starter codePython

def augment_one(L, adj, match_left, match_right):
    # Your code here
    pass

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