二分图：又称二部图，如果一个图的所有顶点可以被分为X和Y两个集合，并且所有边的两个顶点恰好一个属于一个集合X，另一个属于集合Y，即每个集合内的顶点没有边相连，那么这个图就是二分图。 二分图的最大分配问题就是，在所有的分配中，可以输出分配数最多的，但是这样的求解方式效率很低。下面我们引入“增广路”的概念 增广路的本质就是一条路径的起点和终点都是未被配对的点，增加一条增广路就是增加一条配对路线。而当图中已经找不到增广路的时候，就是当前匹配达到了最大匹配。 Input; 6 5 1 4 1 5 2 5 2 6 3 4 Output: 3 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.Scanner;
public class two3 {
    static int[][] e = new int[101][101];
    static int[] match = new int[101];
    static int[] book = new int[101];
    static int n, m;
    static int sum = 0;
    static Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= m; i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            e[x][y] = 1;
            e[y][x] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                book[j] = 0;
            }
            if (dfs(i)) {
                sum++;
            }
        }
        System.out.print(sum);
    }

    private static boolean dfs(int u) {
        for (int i = 1; i <= n; i++) {
            if (book[i] == 0 && e[u][i] == 1) {
                book[i] = 1;
                if (match[i] == 0 || dfs(match[i])) {
                    match[i] = u;
                    match[u] = i;
                    return true;
                }
            }
        }
        return false;
    }
}