二分图全面学习笔记

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int f,t;
};
edge edges[100000];
struct node
{
	int num;
	int col;
	vector<int> to;

};
node nodes[100000];
int n,m;
int tag=1;
bool continue_tag=1;//是否有两个相同节点染上了相同颜色 
void dfs(int x)//x 表示现在在哪个节点
{
	int col=nodes[x].col;
	int to;
	for(int yy=0; yy<nodes[x].to.size(); yy++)
	{
		if(continue_tag)//如果还要继续的话 
		{
			to=edges[nodes[x].to[yy]].t;
			if(nodes[to].col==0)//如果还没有染色过 
			{
				nodes[to].col=3-col;//染上相反颜色 
				dfs(to);//递归遍历 
			}
			else//被染色过 
			{
				if(nodes[to].col==col)//如果颜色相同 
				{
					continue_tag=0;//已经不是二分图了，所以不用再继续了 
					return;
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	int a,b;
	for(int yy=1; yy<=m; yy++)
	{
		cin>>a>>b;
		edges[yy].f=a;
		edges[yy].t=b;
		edges[yy+m].f=b;
		edges[yy+m].t=a;
		nodes[a].to.push_back(yy);
		nodes[b].to.push_back(yy+m);
	}
	for(int ww=1; ww<=n; ww++)//防止图不连通 
	{
		if(nodes[ww].col==0)
		{
			continue_tag=1;
			dfs(ww);
			if(continue_tag==0)
			{
				tag=0;
				break; 
			}

		}
	}
	if(tag==0)
	{
		cout<<"No";
	}
	else
	{
		cout<<"Yes";
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,e;
struct edge
{
	int f,t;
};
edge edges[100000];
struct node
{
	vector<int> to;
	int match;
	bool vis;
	
};
node nodes[100000];
bool dfs(int x)
{
	int to;
	for(int ww=0;ww<nodes[x].to.size();ww++)//遍历这个点的所有能够到达的点 
	{
		to=edges[nodes[x].to[ww]].t;//能到的点 
		if(nodes[to].vis)//如果要去的点被遍历过 
		{
			continue;
		}
		nodes[to].vis=1;//标记要去的点 
		if(nodes[to].match==0||dfs(nodes[to].match))//如果要去的点没被匹配 或者 与其匹配的点还有别的选择即还能和别的点匹配 
		{
			nodes[to].match=x;//这两个点匹配 
			return 1;//返回可行 
		}
	}
	return 0;//不可行 
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m>>e;
	int a,b;
	for(int ww=1; ww<=e; ww++)
	{
		cin>>a>>b;
		edges[ww].f=a;
		edges[ww].t=b;
		edges[ww+e].f=b;
		edges[ww+e].t=a;
		nodes[a].to.push_back(ww);
		nodes[b+n].to.push_back(ww+e);
	}
	int ans=0;
	for(int q=1;q<=n;q++)
	{
		for(int yy=1;yy<=m;yy++)
		{
			nodes[yy].vis=0;
		}
		if(dfs(q))
		{
			ans++;
		}
	}
	cout<<ans;


	return 0;
}

考虑如下构造：从左侧未匹配的节点出发，按照匈牙利算法中增广路的方式走，即先走一条未匹配边，再走一条匹配边。由于已经求出了最大匹配，所以这样的「增广路」一定以匹配边结束，即增广路是不完整的。在所有经过这样「增广路」的节点上打标记。则最后构造的集合是：所有左侧未打标记的节点和所有右侧打了标记的节点。

首先，这个集合的大小等于最大匹配。左边未打标记的点都一定对应着一个匹配边（否则会以这个点为起点开始标记），右边打了标记的节点一定在一条不完整的增广路上，也会对应一个匹配边。假设存在一条匹配边左侧标记了，右侧没标记，左边的点只能是通过另一条匹配边走过来，此时左边的点有两条匹配边，不符合最大匹配的规定；假设存在一条匹配边左侧没标记，右侧标记了，那就会从右边的点沿着这条匹配边走过来，从而左侧也有标记。因此，每一条匹配的边两侧一定都有标记（在不完整的增广路上）或都没有标记，匹配边的两个节点中必然有一个被选中。

其次，这个集合是一个点覆盖。由于我们的构造方式是：所有左侧未打标记的节点和所有右侧打了标记的节点。假设存在左侧打标记且右侧没打标记的边，对于匹配边，上一段已经说明其不存在，对于非匹配边，右端点一定会由这条非匹配边经过，从而被打上标记。因此，这样的构造能够覆盖所有边。

同时，不存在更小的点覆盖。为了覆盖最大匹配的所有边，至少要有最大匹配边数的点数。

证明方式来自 OIwiki