Job Assignment Fair — Solution & Editorial

Back to the Problem

Kuhn's augmenting-path algorithm: for each worker DFS for an augmenting path over alternating edges. Hopcroft–Karp does O(E√V), but Kuhn passes comfortably here.

Complexity: O(V · E)

Watch out: The 'seen' array resets PER worker, not per DFS call — sharing it across workers breaks augmentation.