二分图

二分图：将图中所有点分成两个集合，所有边只会出现在集合之间。
二分图一定不含奇数环

染色法判断二分图

#include 
using namespace std;
const int N = 1e5 + 10;
int n, m, color[N];
vector  g[N];
bool dfs(int u, int c){
	color[u] = c;
	for (auto v : g[u]){
		if (!color[v]){
			if (!dfs(v, 3 - c)) return false;
		}
		else if (color[v] == c) return false;
	}
	return true;
}
int main(){
	cin >> n >> m;
	for (int i = 0; i < m; i ++ ){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bool f = true;
	for (int i = 1; i <= n; i ++ ){
		if (!color[i]){
			if (!dfs(i, 1)){
				f = false;
				break;
			}
		}
	}
	if (f) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

acwing 模板： https://www.acwing.com/problem/content/862/

匈牙利算法找最大匹配

#include 
using namespace std;
const int N = 510;
vector  g[N];
int n1, n2, m, match[N], ans;
bool st[N];
bool find(int x){
	for (auto y : g[x]){
		if (!st[y]){
			st[y] = true;
			if (match[y] == 0 || find(match[y])){
				match[y] = x;
				return true;
			}
		}
	}
	return false;
}
int main(){
	cin >> n1 >> n2 >> m;
	for (int i = 1; i <= m; i ++ ){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
	}
	for (int i = 1; i <= n1; i ++ ){
		memset(st, false, sizeof st);
		if (find(i))
			ans++;
	}
	cout << ans << "\n";
	return 0;
}

acwing 模板： https://www.acwing.com/problem/content/863/
luogu 模板：https://www.luogu.com.cn/problem/P3386