Daily Archives: May 13, 2021

public int findMaxMatch(boolean[][] graph) {
    int match = 0;
    int[] match = new int[graph[0].length];

    for (int i = 0; i < graph.length; i++) {
        boolean[] visited = new int[graph.length];
        if (find(i, graph, match, visited)) {
            match++;
        }
    }
    return match;
}

// match[j], for each record j in B set, it matches to a certain record in A set.
boolean find(int i, boolean[][] graph, int[] match, boolean[] visited) {
    for (int j = 0; j < graph[0].length; j++) {
        if (!graph[i][j] || visited[j]) {
            continue;
        }
        visited[j] = true;
        if (match[j] == -1 || find(match[j], graph, match, visited)) {
            match[j] = i;
            return true;
        }
    }
    return false;
}

讲解. https://youtu.be/beVpSBo7FZk