Place as many applicants as possible

import sys

def max_matching(matrix):
    sys.setrecursionlimit(10000)
    n, m = len(matrix), len(matrix[0])
    holder = [-1] * m                     # holder[j]: applicant currently in job j

    def try_assign(a, tried):
        for j in range(m):
            if matrix[a][j] and not tried[j]:
                tried[j] = True
                if holder[j] == -1 or try_assign(holder[j], tried):
                    holder[j] = a         # augmenting path found: a takes job j
                    return True
        return False

    return sum(1 for a in range(n) if try_assign(a, [False] * m))

#include <functional>
#include <vector>

int solve(const std::vector<std::vector<int>>& matrix) {
    const int n = matrix.size(), m = matrix[0].size();
    std::vector<int> holder(m, -1);              // applicant in each job
    std::vector<bool> tried;
    std::function<bool(int)> tryAssign = [&](int a) {
        for (int j = 0; j < m; ++j) {
            if (!matrix[a][j] || tried[j]) continue;
            tried[j] = true;
            if (holder[j] == -1 || tryAssign(holder[j])) { holder[j] = a; return true; }
        }
        return false;
    };
    int placed = 0;
    for (int a = 0; a < n; ++a) {
        tried.assign(m, false);                  // a fresh search per applicant
        if (tryAssign(a)) ++placed;
    }
    return placed;
}

class Solution {
    private int[][] matrix;
    private int[] holder;
    private boolean[] tried;

    private boolean tryAssign(int a) {
        for (int j = 0; j < holder.length; j++) {
            if (matrix[a][j] == 0 || tried[j]) continue;
            tried[j] = true;
            if (holder[j] == -1 || tryAssign(holder[j])) { holder[j] = a; return true; }
        }
        return false;
    }

    public int maxMatching(int[][] matrix) {
        this.matrix = matrix;
        holder = new int[matrix[0].length];
        java.util.Arrays.fill(holder, -1);           // applicant in each job
        int placed = 0;
        for (int a = 0; a < matrix.length; a++) {
            tried = new boolean[holder.length];      // a fresh search per applicant
            if (tryAssign(a)) placed++;
        }
        return placed;
    }
}

function maxMatching(matrix) {
  const n = matrix.length, m = matrix[0].length;
  const holder = new Array(m).fill(-1);     // applicant in each job
  const tryAssign = (a, tried) => {
    for (let j = 0; j < m; j++) {
      if (!matrix[a][j] || tried[j]) continue;
      tried[j] = true;
      if (holder[j] === -1 || tryAssign(holder[j], tried)) { holder[j] = a; return true; }
    }
    return false;
  };
  let placed = 0;
  for (let a = 0; a < n; a++) if (tryAssign(a, new Array(m).fill(false))) placed++;
  return placed;
}

fn solve<const M: usize>(matrix: &[[i64; M]]) -> i64 {
    fn try_assign<const M: usize>(a: usize, matrix: &[[i64; M]], holder: &mut Vec<Option<usize>>, tried: &mut Vec<bool>) -> bool {
        for j in 0..M {
            if matrix[a][j] == 0 || tried[j] {
                continue;
            }
            tried[j] = true;
            let free = match holder[j] {
                None => true,
                Some(h) => try_assign(h, matrix, holder, tried),
            };
            if free {
                holder[j] = Some(a);                  // a takes job j
                return true;
            }
        }
        false
    }
    let mut holder = vec![None; M];
    let mut placed = 0;
    for a in 0..matrix.len() {
        let mut tried = vec![false; M];               // a fresh search per applicant
        if try_assign(a, matrix, &mut holder, &mut tried) {
            placed += 1;
        }
    }
    placed
}

import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: [[Int]] -> Int
solve matrix = fst (foldl place (0, M.empty) [0 .. length matrix - 1])
  where
    wants a = [j | (j, 1) <- zip [0 ..] (matrix !! a)]
    -- the state is (number placed, map from job to its applicant)
    place (k, holder) a = case tryAssign a S.empty holder of
      Right holder' -> (k + 1, holder')
      Left _ -> (k, holder)
    -- Right: the holders after an augmenting path; Left: the jobs tried, shared across the search
    tryAssign a tried holder = go (wants a) tried
      where
        go [] tr = Left tr
        go (j : js) tr
          | S.member j tr = go js tr
          | otherwise = case M.lookup j holder of
              Nothing -> Right (M.insert j a holder)
              Just h -> case tryAssign h (S.insert j tr) holder of
                Right holder' -> Right (M.insert j a holder')
                Left tr' -> go js tr'