二部(分)图

定义： 二部图是一种特殊的图，可以将图的节点分为2个几个，且每个集合中，节点之间没有关联。大概长这个样子：

理论判断：

• 图 G 中至少存在两个点，且图中所有回路的长度均为偶数。
• 任何无回路的的图均是二分图。

判断图为二部图的方法：染色法

定义：对每一个顶点dfs，对本身染色为1，对其邻点染色成2，若存在其本身与其相邻的节点的颜色相同，则不是二分图，否则是二分图。
例题：AcWing 860. 染色法判定二分图
代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+11;
vector<int>e[N];
int color[N];
bool dfs(int x,int c)
{
	color[x]=c;
	for(int i=0;i<e[x].size();i++)
	{
		int j=e[x][i];
	    if(!color[j])
		{
			if(!dfs(j,3-c))
			  return 0;
		}
		if(color[x]==color[j])
		  return 0;
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!color[i])
		{
			if(!dfs(i,1))
			{
				cout<<"No";
				return 0;
			}
		}
	}
	cout<<"Yes";
	return 0;
}

Something derived

1. 最大匹配：给定二分图 G 中的所有匹配，所含匹配边数最多的匹配，称为这个图的最大匹配。如图：选择最大匹配的问题即为图的最大匹配问题
   如图，红边就是一个最大匹配
   

2. 完全匹配：一个匹配中，图中每个顶点都与图中某条边相关联，则称此匹配为完全匹配，即一个图的某个匹配中，所有的顶点都是匹配点，就是一个完全匹配。
   显然，由于完全匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突，因此完全匹配一定是最大匹配。

3. 完美匹配：对于一个二分图，左点集与右点集的点数相同，若存在一个匹配，包含左点集、右点集的所有顶点，则称为完美匹配

4. 最优匹配：带权二分图的权值最大的完全匹配称为最佳匹配。

匈牙利算法：

匈牙利算法主要用来解决两个问题：求二分图的最大匹配数和最小点覆盖数。
首先说明2个概念交替路 和增广路：

• 交替路：交替路从一个未匹配点出发，依次经过 非匹配边、匹配边、非匹配边… 形成的路径
• 增广路：如果交替路经过除出发点外的另一个未匹配点，则这条交替路称为增广路）
  如图： 8-4-7-1-5为一交替路； 8-4-7-1-5-2为一增广路
  
  增广路的结论：
• P的路径长度一定为奇数
• 对增广路径编号，所有奇数的边都不在M中，偶数边在M中
• P经过取反操作可以得到一个更大的匹配图，比原来匹配多一个
• 当且仅当不存在关于图M的增广路径，则图M为最大匹配

所以匈牙利算法的思路就是：不停找增广路，并增加匹配的个数

放个例题：二分图的最大匹配
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+11;
int first[N];
struct node
{
	int u,v,nxt;
}e[N];
int n1,n2,m;
int ans=0;
int vis[N];
int cp[N];
bool dfs(int x,int tag)
{
	if(vis[x]==tag)
	  return 0;
 	vis[x]=tag;
	for(int i=first[x];i!=-1;i=e[i].nxt)
	{
		int j=e[i].v;
		if(!cp[j] || dfs(cp[j],tag))
		{
			cp[j]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	cin>>n1>>n2>>m;
	int u,v;
	memset(first,-1,sizeof(first));
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		e[i].u=u;
		e[i].v=v;
		e[i].nxt=first[u];
		first[u]=i;
	}
	for(int i=1;i<=n1;i++)
	{
		 if(dfs(i,i))
		   ans++;
	}
	cout<<ans;
	return 0; 
	
 }