「二分图」笔记

二分图同时满足 不存在奇数环 和 染色法不矛盾。

二分图的判定：染色法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 2e6 + 10;
struct
{
	int to, next;
}e[M];
int top, h[N], color[N], n, m;

void add(int x, int y)
{
	e[++top] = {y, h[x]};
	h[x] = top;
}

bool dfs(int x, int c)
{
	color[x] = c;
	for (int i = h[x]; i ; i = e[i].next)
	{
		int y = e[i].to;
		if (!color[y])
		{
			if (dfs(y, (c == 1 ? 2 : 1))) return true;
		}
		else if (color[y] == c) return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
	{
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	bool flag = false;
	for (int i = 1; i <= n; i ++)
	{
		if (!color[i])
			if (dfs(i, 1))
			{
				flag = true;
				break;
			}		
	}
	cout << (flag ? "No" : "Yes");
	
	return 0;
}

二分图的最大匹配：匈牙利算法（贪心 + dfs）

若二分图中有一子图满足任意两条边没有公共节点，则称为一组匹配，

边数最多的子图为该二分图的最大匹配。

#include <bits/stdc++.h>
#define re register int 
using namespace std;
const int N = 1e3 + 10, M = 5e4 + 10;
struct edge
{
	int to, next;
}e[M];
int top, h[N];
int a, b, m, ans, match[N];
bool vis[N];

inline void add(int x, int y)
{
	e[++ top] = (edge){y, h[x]};
	h[x] = top;
	return;
}

bool dfs(int u)
{
	for (re i = h[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if (vis[v]) continue;
		vis[v] = true;
		if (!match[v] || dfs(match[v]))
		{
			match[v] = u;
			return true;
		}
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> a >> b >> m;
	for (re i = 1; i <= m; i ++)
	{ 
		int x, y; cin >> x >> y;
		add(x, y);
	}
	for (re i = 1; i <= a; i ++)
	{
		memset(vis, false, sizeof(vis));
		if (dfs(i)) ans ++;
	}
	cout << ans; //最大匹配的边数
	
	return 0;
}