二分图算法模板以及简单应用
染色法判断二分图
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。
数据范围
1≤n,m≤10^5
输入样例：
4 4
1 3
1 4
2 3
2 4
输出样例：
Yes二分图有个非常重要的性质：无奇数环。可以理解成一个充要条件：无奇数环的无向图一定是二分图，二分图一定没有奇数环
代码模板
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int color[N];
vector<int> e[N];
int n,m;
bool dfs(int u,int v){
color[u] = v;
for(auto x : e[u]){
if(!color[x]){
if(!dfs(x,3 - v)) return false;
}else if(color[x] == v) return false;
}
return true;
}
int main()
{
cin >> n >> m;
for(int i = 0,a,b;i < m;i ++){
cin >> a >> b;
e[a].push_back(b),e[b].push_back(a);
}
bool check = true;
for(int i = 1;i <= n;i ++){
if(!color[i]){
if(!dfs(i,1)){
check = false;
break;
}
}
}
if(check) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}二分图的最大匹配
给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1、 n2 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 uu 和右半部点集中的点 vv 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
1≤n1,n2≤500
1≤u≤n1
1≤v≤n2
1≤m≤10^5
输入样例：
2 2 4
1 1
1 2
2 1
2 2
输出样例：
2匹配问题可以转换成找配偶问题，一个人只能找一个配偶，随便举个例子
比如我们要找这张图的最大匹配，一步步来从第一个点开始找
第一个点找到了配偶，但是他还有一个备选，看第二个点
第二个点也找到了，有一个备选
由于第三个点只有一个能选的，所以他把第二个点的配偶抢了，然后第二个去找了备选，这就是贪心的寻找最大匹配数量，剩下的所有点都是按这个方法找
代码模板
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 510;
int match[N];
bool st[N];
vector<int> e[N];
int n1,n2,m;
int res = 0;
bool find(int u){
for(auto x : e[u]){
if(!st[x]){
st[x] = true;
if(!match[x] || find(match[x])){
match[x] = u;
return true;
}
}
}
return false;
}
int main()
{
cin >> n1 >> n2 >> m;
for(int i = 0,a,b;i < m;i ++){
cin >> a >> b;
e[a].push_back(b);
}
for(int i = 1;i <= n1;i ++){
memset(st,false,sizeof(st));
if(find(i)) res ++;
}
cout << res << endl;
return 0;
}封锁阳光大学
题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由 n 个点构成的无向图，n 个点之间由 m 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入格式
第一行两个正整数，表示节点数和边数。 接下来 m 行，每行两个整数 u,v，表示点 u 到点 v 之间有道路相连。
输出格式
仅一行如果河蟹无法封锁所有道路，则输出 Impossible，否则输出一个整数，表示最少需要多少只河蟹。
输入输出样例
输入 #1复制
3 3 1 2 1 3 2 3
输出 #1复制
Impossible
输入 #2复制
3 2 1 2 2 3
输出 #2复制
1
说明/提示
【数据规模】
对于 100%的数据，1≤n≤10^4，1≤m≤10^5，保证没有重边。
这道题是一个染色法判断二分图的一个简单应用，首先如果有奇数环，那说明不可能满足题目条件（非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。）所以先判断这张图是否是二分图，下一步因为二分图只有两种颜色，定义为1和2（看个人习惯吧）我们只需要在每一个连通块当中找min(cnt_1,cnt_2)加到res当中就是答案了
代码
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int color[N];
vector<int> e[N];
int n,m;
int res = 0;
bool dfs(int u,int v,int &cnt1,int &cnt2){
if(v == 1) cnt1 ++;
else cnt2 ++;
color[u] = v;
for(auto x : e[u]){
if(!color[x]){
if(!dfs(x,3 - v,cnt1,cnt2)) return false;
}else if(color[x] == v) return false;
}
return true;
}
int main()
{
cin >> n >> m;
for(int i = 0,a,b;i < m;i ++){
cin >> a >> b;
e[a].push_back(b),e[b].push_back(a);
}
bool check = true;
for(int i = 1;i <= n;i ++){
if(!color[i]){
int cnt1 = 0,cnt2 = 0;
if(!dfs(i,1,cnt1,cnt2)){
check = false;
break;
}
res += min(cnt1,cnt2);
}
}
if(!check){
cout << "Impossible" << endl;
return 0;
}
cout << res << endl;
return 0;
}加油