题目描述

啥都不要说，这比喻真现实。hh

Java代码

/*
 yls奇妙比喻，左半部比作男孩，右半部比作女孩
 时间复杂度：最坏O(nm)，但是一般情况下，效果非常好
*/

import java.util.*;

public class Main {
    static int N = 510, M = 100010;
    static int n1, n2, m;
    static int h[] = new int[N], e[] = new int[M], ne[] = new int[M], idx = 0;
    // match[i]:不为0，就标志i被右半部的一个点匹配了，存的值是：与i相匹配的左边点
    static int[] match = new int[N];
    // 这个是在find(match[j])的时候起作用，表达的意思是，我让出这个女孩，看是否还有其他的女孩可以和我匹配
    // st[i]：为true表示，在某一轮的匹配中右半部的i号点已经被匹配了。在某一轮（主函数中的一次for循环）起作用
    static boolean[] st = new boolean[N];

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

    static boolean find(int x) {

        // 遍历当前点指向右半部的点。(就是找当前男生是否能够找到一个女朋友)
        for(int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            // 如果这一次轮次女生还没有找到男朋友，就可以参加匹配
            if(!st[j]) {
                st[j] = true;
                /* 如果当前这个右半部的点j没有被匹配，则左半部的点x可以匹配这个点
                 * 或者当前match[j]可以匹配其它右边的点（也就是原来左半部与j相匹配的点，
                 * 可以去匹配其它右半部的点）,
                 *  则左半部的点x也可以匹配这个点，返回匹配成功
                 * 
                 */
                if(match[j] == 0 || find(match[j])) {
                    // 匹配成功
                    match[j] = x;
                    return true;
                }
            }
        }
        // 表示当前点找不到一个右半部的点与之相匹配
        // 表示当前男生找不到一个女朋友
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n1 = sc.nextInt(); n2 = sc.nextInt(); m = sc.nextInt();

        // 邻接表的必要初始化
        Arrays.fill(h, -1);
        while(m -- > 0) {
            int a = sc.nextInt(), b = sc.nextInt();
            // 虽然是无向图，由于只要记左半部往右半部的连线，所以只需要添加一边即可
            add(a, b);
        }
        int res = 0;
        for(int i = 1; i <= n1; i ++) {
            // 只要一次for循环起作用，所以下一次for循环的时候必须重新赋初值
            Arrays.fill(st, false);
            // 如果当前i这个点匹配成功，就让计数加一
            if(find(i)) res ++;
        }
        System.out.println(res);
    }
}