二分图

一个图是二分图当且仅当图中不含有奇数环

染色法判定二分图：

由于图中不含有奇数换，所以染色过程一定没有矛盾

• 如果一个图可以用二染色进行染色，没有矛盾，则图是二分图
• 用到的点：深度优先或者广度优先遍历，链表法存图
• 注意的点：图不是连通图，所以每一个点都要在主函数遍历一遍

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100010;
    static int M = 200010;
    static int[]g = new int[N], color = new int[N];
    static int []e = new int[M], ne = new int[M];

    static int idx = 0;
    static boolean flag = true;
    public static void main(String []args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String []line = reader.readLine().split("\\s+");
        int n = Integer.parseInt(line[0]), m = Integer.parseInt(line[1]);
        while(m-->0){
            String []list = reader.readLine().split("\\s+");
            int a = Integer.parseInt(list[0]), b = Integer.parseInt(list[1]);
            //无向图添加两次边
            add(a,b);
            add(b,a);
        }
        for(int i = 1;i<=n;i++){
            if(color[i]==0){
                if(!dfs(i,1)) {
                    flag = false;
                    break;
                }
            }
        }
        if(flag) System.out.println("Yes");
        else System.out.println("No");
    }

    private static boolean dfs(int id, int colour) {
        if(color[id]==0){
            color[id]=colour;
            for(int i = g[id]; i!= 0;i = ne[i]){
                int tmp = e[i];
                if(!dfs(tmp,3-colour)) return false;
            }
        }
        if (color[id]!=colour) return false;
        return true;
    }

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

匈牙利算法

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class HungaryAlgorithm {
    static int N = 510;
    static int M = 100010;
    static int[] g = new int[N], match = new int[N];
    static int idx;
    static int res;
    static int[] e = new int[M], ne = new int[M];
    static boolean[] st = new boolean[N];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] line = reader.readLine().split("\\s+");
        int n1 = Integer.parseInt(line[0]), n2 = Integer.parseInt(line[1]), m = Integer.parseInt(line[2]);
        while (m-- > 0) {
            String[] list = reader.readLine().split("\\s+");
            int a = Integer.parseInt(list[0]), b = Integer.parseInt(list[1]);
            add(a, b);
        }
        for (int i = 1; i <= n1; i++) {
            Arrays.fill(st, false);
            if (find(i)) res++;
        }
        System.out.println(res);
    }

    private static boolean find(int id) {
        for (int i = g[id]; i != 0; i = ne[i]) {
            int tmp = e[i];
            if (!st[tmp]) {
                st[tmp] = true;
                if (match[tmp] == 0 || find(match[tmp])) {
                    match[tmp] = id;
                    return true;
                }
            }
        }
        return false;
    }


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