二分图
概念详解
二分图： 可以把图中所有顶点分成两个集合 A、B，使得每条边的两个端点分别属于 A 和 B（同一个集合内部没有边）。判断、染色、匹配是二分图的三类核心问题。
判定定理： 一个图是二分图，当且仅当图当中不含有奇数环。
一个图是二分图当且仅当图当中不含有奇数环
染色法判定原理： 用 1、2 两种颜色给顶点染色，要求每条边的两个端点颜色不同（这正是”分属两个集合”的另一种说法）。DFS 交替染色：当前点染 c，邻居就必须染 3-c；若某个邻居已被染成与当前点相同的颜色，说明出现矛盾，图不是二分图。注意图可能不连通，要对每个未染色的连通块都做一次 DFS。
匈牙利算法求最大匹配： 匹配 = 一组两两没有公共端点的边；最大匹配 = 边数最多的匹配。匈牙利算法的直观理解是”给左边每个点找对象”：左边点 x 依次考察它喜欢的右边点 j，若 j 还没配对，直接配对；若 j 已配对，就试着让 j 的现任 match[j] 挪个位置（递归 find(match[j])），挪得动就把 j 让给 x。每次尝试都要用 st 数组标记”本轮已考虑过的右边点”，防止递归死循环。时间复杂度 O(n1 · m)。
染色法
判断是不是二分图
给定一个 n 个点 m 条边的无向图，图中 可能存在重边和自环。 请你判断这个图 是否是二分图。
输入格式
第一行包含两个整数 n 和 m。 接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出
"Yes"，否则输出"No"。数据范围
1 ≤ n, m ≤ 10⁵
import java.util.*;import java.io.*;public class Main{ static int N = 100010; static int M = 200010; static int n ,m; static int[] color = new int[N],h= new int[N],e = new int[M],ne = new int[M]; static int idx;
static void add(int a ,int b){ e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } static boolean dfs(int u ,int c ){ color[u] = c; for(int i = h[u];i!=-1;i = ne[i]){ int j = e[i]; if(color[j] == 0) { if(!dfs(j,3-c)){ return false; } } else if(color[j] == c){ return false; } } return true; } public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nm = br.readLine().trim().split("\\s+"); n = Integer.parseInt(nm[0]); m = Integer.parseInt(nm[1]); Arrays.fill(h,-1); while(m -- > 0){ String[] ab = br.readLine().trim().split("\\s+"); int a = Integer.parseInt(ab[0]); int b = Integer.parseInt(ab[1]); add(a,b); add(b,a); } boolean flag = true; 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"); } }
}匈牙利算法
计算一个图中的最大的匹配数量
给定一个二分图，其中：
- 左半部包含
n1个点（编号 1~n1）- 右半部包含
n2个点（编号 1~n2）- 共包含
m条边数据保证任意一条边的两个端点都不可能在同一部分中。 请你求出二分图的 最大匹配数。
定义
给定一个二分图 G，在 G 的一个子图 M 中，M 的边集中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。 所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数：
n1,n2,m。 接下来m行，每行包含两个整数u和v，表示左边部点集中的点u和右边部点集中的点v之间存在一条边。输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
- 1 ≤ n1, n2 ≤ 500
- 1 ≤ u ≤ n1
- 1 ≤ v ≤ n2
- 1 ≤ m ≤ 10⁵
import java.util.*;import java.io.*;public class Main{ static int n1,n2,m; static int N = 510,M = 100010; static int[] h = new int[N],e= new int[M],ne = new int[M]; static int idx; static int[] match = new int[N]; static boolean[] st = new boolean[N]; static void add(int a,int b){ e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } static boolean find(int x){ for(int i = h[x];i!= -1;i = ne[i]){ int j = e[i]; if(!st[j]){ st[j] = true; if(match[j] == 0 || find(match[j])){ match[j] = x; return true; } } } return false; } public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nm = br.readLine().trim().split("\\s+"); n1 = Integer.parseInt(nm[0]); n2 = Integer.parseInt(nm[1]); m = Integer.parseInt(nm[2]); Arrays.fill(h,-1); while(m-- >0){ String[] ab = br.readLine().trim().split("\\s+"); int a = Integer.parseInt(ab[0]); int b = Integer.parseInt(ab[1]); add(a,b); } int res = 0; for(int i =1;i <= n1;i++){ Arrays.fill(st,false); if(find(i)) res++; } System.out.println(res);
}
}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时