3、匈牙利算法 &二分图的最大匹配

AcWing 861. 二分图的最大匹配

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int n1, n2, m;
    int N = 100010;
    int h[] = new int[N];
    int e[] = new int[N];
    int ne[] = new int[N];
    int match[] = new int[N];
    boolean st[] = new boolean[N];
    int idx;

    void insert(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    boolean find(int x) {
        for (int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {//锁住当前的女生，让find判断下一个女生，否则会陷入死循环
                st[j] = true;
                if (match[j] == -1 || find(match[j])) {
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

    void init() {
        Scanner sc = new Scanner(System.in);
        n1 = sc.nextInt();
        n2 = sc.nextInt();
        m = sc.nextInt();
        int res = 0;
        Arrays.fill(h, -1);
        Arrays.fill(st, false);
        Arrays.fill(match, -1);
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            insert(a, b);
        }
        for (int i = 1; i <= n1; i++) {
            Arrays.fill(st, false);
            if (find(i)) res++;
        }
        System.out.println(res);
    }
}