二分图和匈牙利算法
一、二分图
1、思路
通过染色法判断二分图
二分法，就是可以把集合分为2部分，分别在每个集合内不存在边，有边只在两个集合之间。
一个图是二分图当且仅当图中不含有奇数环。
当染色过程中有矛盾时，就不是二分图。
用dfs或bfs遍历通过时染色
2、代码模板：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int color[N];//0代表还没染色，1代表白色，2代表黑色
void add(int a,int b)//添加一条从a到b的点,二分图只用加一个边就行，不用加两条边
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool dfs(int u,int c)//将u染成c的颜色，并且往下继续染色，返回值为0代表有冲突，为1代表没有冲突。
{
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)//如果邻点颜色和u相同，则说明出现奇环，返回false
return false;
}
return true;//图中未发现奇环，是二分图
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d %d",&n,&m);
while(m--)
{
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
add(b,a);
}
bool flag=true;//1代表没有冲突，0代表有冲突
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;
}
3、bfs版
代码思路
颜色 1 和 2 表示不同颜色, 0 表示未染***r />
定义queue是存PII，表示 <点编号, 颜色>,
同理，遍历所有点, 将未染色的点都进行bfs
队列初始化将第i个点入队, 默认颜色可以是1或2
while (队列不空)
每次获取队头t, 并遍历队头t的所有邻边
若邻边的点未染色则染上与队头t相反的颜色，并添加到队列
若邻边的点已经染色且与队头t的颜色相同, 则返回false
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
typedef pair<int, int> PII;
int e[M], ne[M], h[N], idx;
int n, m;
int st[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool bfs(int u){
int hh = 0, tt = 0;
PII q[N];
q[0] = {u, 1};
st[u] = 1;
while(hh <= tt){
auto t = q[hh ++];
int ver = t.first, c = t.second;
for (int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if(!st[j])
{
st[j] = 3 - c;
q[++ tt] = {j, 3 - c};
}
else if(st[j] == c) return false;
}
}
return true;
}
int main(){
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m --){
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
int flag = true;
for(int i = 1; i <= n; i ++) {
if (!st[i]){
if(!bfs(i)){
flag = false;
break;
}
}
}
if (flag) puts("Yes");
else puts("No");
return 0;
}
二、匈牙利算法
1、思路
用来求2个集合之间连接的边的个数
每一个点只属于一个边
就算是无向边，存的边也只存左边的点指向右边的点
match存右边的点对应的左边的点
st防止重复搜点，res存匹配边的数量
遍历左集合的点，寻找匹配的边。
2、代码模板：
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n1,n2,m;//n1左集合,n2右集合
int h[N],e[N],ne[N],idx;
int match[N];//match存右边的点对应的左边的点
bool st[N];//st防止重复搜点,false是没有被遍历。true是被遍历过了
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool find(int x)//寻找第二个集合中与第一个集合x相匹配的下标
{
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])//当j没有匹配时
{
st[j]=true;//标记一下j点已经被遍历
if(match[j]==0||find(match[j]))//当j没有匹配的值时，或者j配对的点有下家时。
{
match[j]=x;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d %d %d",&n1,&n2,&m);
memset(h,-1,sizeof h);
int res=0;
while(m--)
{
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
}
for(int i=1;i<=n1;i++)
{
memset(st,false,sizeof st);
if(find(i))
res++;
}
printf("%d",res);
return 0;
}
