本系列所有题目均为Acwing课的内容，发表博客既是为了学习总结，加深自己的印象，同时也是为了以后回过头来看时，不会感叹虚度光阴罢了，因此如果出现错误，欢迎大家能够指出错误，我会认真改正的。同时也希望文章能够让你有所收获，与君共勉！

今天来学习二分图及其最大匹配，二分图指的是一个图中的点都被分在两个点集中，且点集内部的点不存在边相连接，他们只与另一个点集中的点存在边，这样可以被分为两部分且各部分内部无关的图就被称为二部图/二分图。
二部图的定义：含有奇数环的图一定不是二部图，其逆否命题为二部图一定是不含奇数环的图。
完全二分图指的就是一个集合的每一个点与另一个集合的每一个点都存在边，这样的图就被称为完全二部图，那么怎么来判断一个图是二部图呢？我们可以使用染色法判断二部图。

染色法判断二分图

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式
如果给定图是二分图，则输出 Yes，否则输出No。

数据范围
1≤n,m≤105
输入样例：

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

算法原理

需要注意二部图并不一定是连通图，所以需要判断每个点是否需要染色，并且将这个点所在的连通块都进行染色。
算法步骤：
1.

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5+10,M = 2e5+10;	// 无向图
int e[M],ne[M],h[N],idx;	// 邻接表存图
int color[N];	// 颜色为1和2

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

bool dfs(int u,int c){	// 由一个点的颜色就可以判断其他所有点的颜色
	color[u] = c;
	
	for(int i=h[u] ; i != -1 ; i = ne[i]){	// 遍历所有与u相连的点
		int j = e[i];
		if(!color[j]){	// 对于没有被染色的点
			if(!dfs(j,3-c))	return false;	// 如果这里存在奇数环（发生冲突）说明不能被染色，返回false
		}
		else if(color[j] == c)	return false;	// 如果j的颜色yvu的颜色相同，则发生冲突（j的颜色应该是2但是却是1）
	}
	return true;
}

int main(void){
	int n,m;
	cin >> n >> m;
	memset(h,-1,sizeof h);
	
	
	while(m--){
		int a,b;
		cin >> a >> b ;
		add(a,b);
		add(b,a);
	}
	
	bool flag = true;	// flag表示为ture就是二分图，false就是不是二分图
	for(int i=1; i <= n ; ++i){	// 遍历所有的点从编号为1开始到n
		if(!color[i]){	// 对每个点所在的连通块进行染色，染过的不用染
			if(!dfs(i,1)){	// 如果存在奇数环染色出现冲突则说明不是二分图
				flag = false;
				break;
			}
		}
	}
	
	if(flag){
		puts("Yes");
	}
	else {
		puts("No");
	}
}

整个基础图论终于只剩下二分图的最大匹配也就是匈牙利算法了，时间复杂度好的时候为\(O(m)\)，时间复杂度最差为\(O(mn)\)，由于y总的举例以及匈牙利算法的匹配特性，我在时间复杂度最好时叫他月老算法，时间复杂度中等时叫他牛头人算法，时间复杂度最差时叫他添狗算法