二分图与匈牙利算法
二分图
前置知识
- 图论
- 搜索
难度
题目难度大多数都集中于
引入
二分图 (Bipartite Graph，偶图，二部图) 是一种特殊的图，可以将图中的结点分成两个不相交的集合
定义
前方高能，将会有大量知识点。
-
二分图： 如果图
G =(V,E) 的顶点集V 可以分为两个互不相交的子集X 和Y ，使得每条边e\in E 的两个端点都分别属于X 和Y ， 就称图G 是一个二分图。 -
二分图通常的画法： 通常将二分图的结点画与两边，中间连边，如图
2 ：
-
部分： 集合
X 和Y ， 又称二分图的 左部(X) 和 右部(Y) 。 -
匹配： 二分图中的一个边的集合，集合中边的结点都没有共边，如图
3,4 中的标红的边。 -
匹配点，匹配边，未匹配点，非匹配边： 含义非常显然。如图
3 中1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7 为匹配边，其他边为非匹配边。 -
最大匹配： 一个图所有匹配中，所含匹配边数最多的匹配，称这个图为最大匹配，如图
4 就是最大匹配。 -
完美匹配： 所有结点都为匹配点的图，称为完美匹配图，完美匹配一定是最大匹配，但最大匹配不一定是完美匹配，如图
4 就是完美匹配。 -
最大匹配数： 最大匹配的匹配边的数量。
-
最小点覆盖数： 选取最少的结点，使得任意一条边至少有一个端点被选择。
-
最大独立数： 与最小点覆盖数相反，选取最多的结点，使得任意两个被选结点都不相连。
-
最小路径覆盖数： 选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为
0 （即单个点）。 -
交替路： 从未匹配点出发,依次经过非匹配边，匹配边，非匹配边，匹配边……形成的路径称为交替路。
-
增广路： 从未匹配点出发,走交替路，不同的是，增广路的路径经过的结点必须是匹配点，如果是未匹配点，则这条路就为增广路，如图
5 中的一条增广路如图6 所示（图中的匹配点均用红色标出）：
性质
-
如果将二分图的每个结点染色，只需要两种颜色即可。
-
二分图中，不包含奇数长度的环。
- 很显然，第一条性质与二分图的定义等价：只需要将二分图的两个部分各染一种颜色就好了。
如何判断二分图
思路
只需要使用二分图的第一条性质即可，我们直接使用搜索跑一边图，边跑边染色，如果有图无法染色，就可以知道这张图一定不是二分图了。
代码实现
::::info[代码]
#include<bits/stdc++.h>
using namespace std;
const int kN = 1e5 + 7;
int n, m;
int dis[kN];
bool vis[kN];
vector<int>g[kN];
void Clear(){ //清空
for(int i = 1; i <= n; ++i){
g[i].clear();
}
fill(dis + 1, dis + 1 + n, 0);
fill(vis + 1, vis + 1 + n, 0);
return ;
}
bool dfs(int s){
vis[s] = 1;
for(auto x: g[s]){
if(vis[x]){
if(dis[s] == dis[x]){
return 0;
}
}else{
dis[x] = dis[s] ^ 1;
if(!dfs(x)){
return 0;
}
}
}
return 1;
}
bool check(){
for(int i = 1; i <= n; ++i){ //枚举每一个点
if(!vis[i]){
dis[i] = 0;
if(!dfs(i)){
return 0;
}
}
}
return 1;
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
bool flag = check();
if(flag){
cout << "Yes\n";
}else{
cout << "No\n";
}
return ;
}
signed main(){
cin.tie(0) -> ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
solve();
Clear();
}
return 0;
}::::