二分图
1. 定义
二分图 (Bipartite graph), 所有的点被分为 U, V 两个集合, 使得所有的边都满足: 一个点在 U 中, 另一个点在 V 中.
2. 性质
- U, V 集合内部没有边
- 不存在长度为奇数的环
3. 判定方法
graph LR
选择深搜或广搜 --> 遍历图
遍历图 --> |存在奇环| 不是二分图
遍历图 --> |不存在奇环| 是二分图
4. 最大匹配
| 概念 | 定义 |
|---|---|
| 匹配 | 图的一个子集，任意两条边没有公共顶点，点为匹配点，边为匹配边 |
| 最大匹配 | 边数最多的匹配 |
| 完美匹配 | 所有点均为匹配点的匹配 |
| 交替路 | 从匹配点出发，依次经过非匹配边、匹配边、非匹配边等的路径 |
| 增广路 | 从匹配点出发，沿着交替路走，非匹配边比匹配边多一条，可改进匹配 |
| 最少点覆盖数 | 选择最少的点，使每条边至少有一个端点被选择 |
- 最大匹配数 = 最少点覆盖数
4.1. 相互喜欢的最大匹配问题
题目
多个男女, 已知每个人喜欢的对象, 最多可配几对, 使得每对间都相互喜欢.
解法
匈牙利算法: 从一未匹配边开始, 运行 DFS 来扩充增广路
实现
#pragma once
/**
* @file bipartite_graph_maximum_matching.h
* @brief 相互喜欢的最大匹配问题
* @author gendloop
*/
// c++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
class BipartiteGraphMaximumMatching {
private:
std::unordered_map<int, std::unordered_set<int>> graph_;
std::unordered_map<int, int> match_;
int count_;
public:
BipartiteGraphMaximumMatching() = default;
inline void setGraph(const std::unordered_map<int, std::unordered_set<int>>& graph) {
graph_ = graph;
}
void search() {
count_ = 0, match_.clear();
for (auto& node : graph_) {
for (int n : node.second)
match_[n] = -1;
}
for (auto& node : graph_) {
std::unordered_map<int, bool> visited;
for (auto& node : graph_) {
for (int n : node.second) {
visited[n] = false;
}
}
if (DFS(node.first, graph_, match_, visited)) {
count_++;
}
}
}
inline void printMatchedResult() const {
for (auto node : match_) {
if (node.second != -1) {
std::cout << node.first << " => " << node.second << std::endl;
}
}
std::cout << std::endl;
}
inline int getCount() const {
return count_;
}
protected:
static bool DFS(int u, const std::unordered_map<int, std::unordered_set<int>>& graph,
std::unordered_map<int, int>& match, std::unordered_map<int, bool>& visited)
{
for (auto p : graph.at(u)) {
if (!visited[p]) {
visited[p] = true;
if (match[p] == -1 || DFS(match[p], graph, match, visited)) {
match[p] = u;
return true;
}
}
}
return false;
}
};