题目描述

二分图的最大匹配

JAVA 代码

/**
解题思路：
寻找二分图的最大匹配问题思路就是遍历所有左边集合的点，
如果可以为它们找到一个匹配点，
结果加加，主要的逻辑在find函数上。

时间复杂度分析：
二分图的匹配问题的理论时间复杂度很高，但是实际运行效率却很好，时间复杂度大致为O(n∗m)
*/
import java.util.*;
import java.io.*;

class Main{
    static int N = 510, M = 100010, n1,n2,m, idx;
    static int[] h = new int[N];
    static int[] e = new int[M], ne = new int[M];
    static int[] match = new int[M];//存储当前的节点匹配的节点的编号
    static boolean[] st = new boolean[M];//表示当前的这个节点是否访问过了

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


    static boolean find(int t){
        for(int i=h[t]; i!=-1; i=ne[i]){
            int j = e[i];
            //访问过了 下一个
            if(st[j]) continue;
            st[j] = true;
            //如果当前节点没有任何匹配的对象,
            //或者, 还能找到另一个匹配对象. 
            if(match[j]==0 || find(match[j])){
                match[j] = t;
                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){
            add(sc.nextInt(),sc.nextInt());
        }
        //记录匹配的个数
        int res = 0;
        for(int i=1;i<=n1;i++){
            Arrays.fill(st, false);
            if(find(i)) res++;
        }
        System.out.println(res);

    }
}