一個(gè)圖是二分圖當(dāng)且僅當(dāng)圖中不含有奇數(shù)環(huán)

染色法判定二分圖：

由于圖中不含有奇數(shù)換错忱，所以染色過程一定沒有矛盾

• 如果一個(gè)圖可以用二染色進(jìn)行染色霍弹，沒有矛盾谒撼，則圖是二分圖
• 用到的點(diǎn)：深度優(yōu)先或者廣度優(yōu)先遍歷楼咳，鏈表法存圖
• 注意的點(diǎn)：圖不是連通圖熄捍，所以每一個(gè)點(diǎn)都要在主函數(shù)遍歷一遍

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;
    }
}