# 什么是二分图？
二分图的结点由两个集合组成，且两个集合内部没有边，如下图所示：
![]()
# 二分图的性质（等价）
- 如果对于图中点进行染色，那么每一条边一定连接着一个红色点和一个蓝色点
- 二分图中不存在长度为奇数的环
- 因为染色性质，每条边都是从一个集合走到另一个集合，要走偶数次才能回到同一个集合
- 不存在奇数环，一定是二分图
# 怎么判定二分图？
题目传送门
遍历所有点：
- 如果当前点没被染色，则将该点染成颜色 1，并且 DFS 该点能搜到的所有点，进行相邻染色
- 对于搜索过程中，如果搜到了相邻点已经被染色并且染的是相同颜色，则代表这个图不是二分图
可以利用 1 和 2 来当作两个颜色， 3 = 1 + 2 的特性使得可以很方便地在两个颜色直接的切换
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| int n, m;
int color[N];
vector<int> g[N];
bool dfs(int u, int c) {
color[u] = c;
for (auto to : g[u]) {
if (color[to] == 0 && !dfs(to, 3 - c))
return false;
else if (color[to] == c)
return false;
}
return true;
}
void solve () {
cin >> n >> m;
for (int i = 1, a, b; i <= m; i++) {
cin >> a >> b;
g[a].push_back(b), g[b].push_back(a);
}
for (int i = 1; i <= n; i++)
if (color[i] == 0 && !dfs(i, 1)) {
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
}
|
# 应用
# 二分图的最大匹配
题目传送门
简化题目：现有 n1 个男生和 n2 个女生，男女之间的边代表彼此互相有好感（有好感就能成为对象？也许吧？），求其中能凑出的最大数量的情侣对数
相互有好感，语义上应该是无向图
做这题的时候，为了避免被女拳出击，我们建图的时候只考虑女生对男生的好感，也就是建女生到男生的单项图
遍历所有女生，如果当前女生能找到对象，则计数 cnt 加一，那么怎么样算能找到对象呢？
- 如果有喜欢的男生，并且这个男生没女朋友，那么算找到对象
- 如果有喜欢的男生，但他有女朋友，问问这个男生现在的女朋友能不能换个男朋友，可以的话就算找到对象
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| int n1, n2, m, u, v, cnt = 0;
vector<int> g[520];
bool st[520];
int match[520];
bool find(int x) {
for (auto to : g[x])
if (!st[to]) {
st[to] = true;
if (match[to] == 0 || find(match[to])) {
match[to] = x;
return true;
}
}
return false;
}
void solve () {
cin >> n1 >> n2 >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v;
g[v].push_back(u);
}
for (int i = 1; i <= n2; i++) {
memset(st, false, sizeof st);
if (find(i))
cnt++;
}
cout << cnt << endl;
}
|
