图论——二分图
二分图通俗解释
有一个图，将顶点分成两类，边只存在不同类顶点之间，同类顶点之间设有边。称图 G 为二部图，或称二分图，也称欧图。
性质
- 二分图不含有奇数环
- 图中没有奇数环，一定可以转换为二分图
判断二分图——染色法（dfs）
可以用二染色方式染色，那么就是二分图
代码
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出
Yes，否则输出No。
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
// 链式前向星
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
// 各个点的颜色，0 未染色，1 是红色，2 是黑色
int color[N];
bool 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]) {
if (!dfs(j, 3 - c))
return false;
}
else if (color[j] == c) return false;
}
return true;
}
int main() {
memset(h, -1, sizeof h);
int n, m;
cin >> n >> m;
while (m --) {
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
bool flag = true;
for (int i = 1; i <= n; i ++) {
if (!color[i]) {
if (!dfs(i, 1)) {
flag = false;
break;
}
}
}
if (flag) puts("Yes");
else puts("No");
return 0;
}
二分图的最大匹配——匈牙利算法(详细证明请见《算法导论》)
匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替 路称为增广路（agumenting path）。
代码
输入格式
第一行包含三个整数 n1、 n2 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 100010;
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
int match[N];
bool st[N];
bool 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] || find(match[j])) {
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
memset(h, -1, sizeof h);
int n1, n2, m;
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 ++) {
memset(st, 0, sizeof st);
if (find(i)) res ++;
}
cout << res << endl;
return 0;
}
