二分图指的是,把图中所有的点划分成两个集合。集合内部不存在边,边只存在两个集合之间。这个有点像鞋带的就是二分图。
image.png
二分图的一个性质:一个图是二分图,当且仅当图中不包含奇数环(指环中的边的数量是奇数)。因为,我们很可以推测出当存在一个奇数环,我们不可能把一个点划分到两个集合中。图下就矛盾了。该点不能同时划分到1集合和2集合。
image.png

image.png

染色法(判断二分图)

算法思想

  • 前提:我们知道,当一个连通块,确定了所属集合,整个联通块中的所有点的集合都是确定的。
    • image.png
  • 根据上面的性质,和二分图性质,可以判断出。当图中存在奇数环,那么必然有两个点被分在同一个集合中。

模板题

  • 染色法判定二分图

  • image.png

  • 题目分析:题目要求我们使用判断该图是否是二分图,那么利用性质,使用染色法。观察数据范围,该图是一个稀疏图,应该用邻接表存储边。

  • 解题代码:

    • 
      	#include <iostream>
      	#include <algorithm>
      	#include <cstring>
      	using namespace std;
      
      	const int N = 2e5 + 10;
      	int h[N], ne[N], e[N], idx;
      	int n, m;
      	// 为每个点划分集合
      	int colors[N];
      
      	void add(int a, int b) {
      		e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
      	}
      
      	bool dfs(int u, int c) {
      		// 将u划分到c集合
      		colors[u] = c;
      		// 在划分它的子结点到另一个集合
      		for (int i = h[u]; i != -1; i = ne[i]) {
      			int j = e[i];
      			// 如果未划分
      			if (!colors[j]) {
      				// 则划分
      				if (!dfs(j, 3-c))
      					return false;
      				// 如果已经划分了集合,判断两个点的集合否相等。相等则存在奇数环,那么就不是二分图
      			} else if (colors[j] == c)
      				return false;
      		}
      		return true;
      	}
      
      	int main() {
      		memset(h, -1, sizeof h);
      
      		cin >> n >> m;
      		while(m --) {
      			int a, b;
      			cin >> a >> b;
      			add(a, b);
      			add(b, a);
      		}    
      
      		int flag = false;
      		for (int i = 1; i <= n; ++ i) {
      			// 如果当前点未划分集合,则划分
      			if (!colors[i]) {
      				if (!dfs(i, 1)) {
      					flag = true;
      					break;
      				}
      			}
      		}
      		if (flag)
      			puts("No");
      		else
      			puts("Yes");
      		return 0;
      	}
      

匈牙利二分图匹配

二分图匹配:指的是让途中任意两条边,不存在同一个点。也就是每个点一对一专一。匹配就是计算存在多少条能够这样分配的边。

算法思想:匈牙利算法的过程,就是当某一点已经和另外一点匹配了。但是,这一点又是当前一点的唯一匹配。那么,就让这一点的匹配的点,去找它其他匹配的点,把这个点让给当前的点。如果这一点匹配的点,没有备用点,当前点就匹配失败。

图解

  • image.png
  • 1 这个图,红色表示当前已经匹配的。
  • 2 图,紫色表示当前有点的唯一匹配和其他点相同。
  • 3 图,绿色的线表示,将已经匹配的点让给了,唯一匹配的点。
  • 4 图,红色表示,慷概的点找到它的备用点。

模板题

  • 二分图的最大匹配
  • image.png
  • 题目解析:此题是为了求,能够满足一对一配对的点最多有几对。
  • 解题代码:
    • 
      	#include <iostream>
      	#include <algorithm>
      	#include <cstring>
      	using namespace std;
      
      	const int N = 1e5 + 5;
      	int h[N], ne[N], e[N], idx;
      	// 当前待匹配的点
      	int matchs[N];
      	bool st[N];
      	int n1, n2, m;
      
      	void add(int a, int b) {
      		e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
      	}
      
      
      	bool find(int u) {
      		for (int i = h[u]; i != -1; i = ne[i]) {
      			int j = e[i];
      			// 如果当前这个点没有考虑过
      			if (!st[j]) {
      				st[j] = true;
      				// 如果当前这个点没有对象,或者它的对象有备胎,那么u就可以正式上位
      				if (!matchs[j] || find(matchs[j])) {
      					matchs[j] = u;
      					return true;
      				}
      			}
      		}
      
      		return false;
      	}
      
      	int main() {
      		memset(h, -1, sizeof h);
      		cin >> n1 >> n2 >> m;
      		while(m --) {
      			int a, b;
      			cin >> a >> b;
      			add(a, b);
      		}
      		int res = 0;
      		// 为每个点尝试一对一牵手配对
      		for (int i = 1; i <= n1; ++ i) {
      			// st 保存的右边集合中i这个点没有考虑过的点
      			memset(st, false, sizeof st);
      			if (find(i))
      				res ++;
      		}
      
      		cout << res << endl;
      		return 0;
      	}