01 二分图判定 （不一定考）

DFS 染色法

02 二分图最大匹配

• 洛谷 3386

package double1;
import java.beans.Visibility;
import java.util.*;

public class Double {
	static int idx=0;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int k = scan.nextInt();
		int[] h = new int[k+10];
		int[] vis = new int[n+m+10];
		int[] match = new int[k+10];
		
		Edge[] e = new Edge[1<<20]; //初始化结构体，防止空指针异常
		for (int i = 0; i <= 20; i++) {
		    e[i] = new Edge(0, 0); 
		}
		
		int a,b,ans=0,idx=0;
		for(int i=0;i<k;i++) {
			a = scan.nextInt();
			b = scan.nextInt(); //添加单向边
			e[idx].v = b; 
			e[idx].ne = h[a];
			idx++;
			h[a] = idx; 
		}
		
		for(int i=1;i<=n;i++) {
			if (dfs(i, h, vis, e, match))
				ans++;
		}
		System.out.println(ans);
	}
	
	public static boolean dfs(int u,int[] h,int[] vis,Edge[] e,int[] match) {
		for (int i=h[u];i!=0;i=e[i].ne) {
			int v=e[i].v;
			if (vis[v] != 0) {
				continue;
			}
			vis[v]=1;
			if(match[v]==0 || dfs(match[v], h, vis, e, match)) {
				match[v] = u;
				return true;
			}
		}
		return false;
	}
	
	static class Edge{
		int v;
		int ne;
		public Edge(int v,int ne) {
			 this.v = v;
			 this.ne = ne;
		}
	}
}