染色法

#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<stack>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+5;
struct node{
	int to,next;
}edge[maxn];
int cnt=1,head[maxn],n,m;
void add(int u,int v)
{
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
} 
int color[maxn];
bool dfs(int u,int c)
{
	color[u]=c;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(!color[v])
		{
			if(!dfs(v,3-c))
				return false;
		}
		else if(color[u]==color[v])
			return false;
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	int flag=1;
	for(int i=1;i<=n;i++)
	{
		if(!color[i])
		{
			if(!dfs(i,1))
			{
				flag=0;
				break;
			}
		}
	}
	if(flag)
		printf("Yes");
	else printf("No");
}

匈牙利算法

#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<stack>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
struct node{
	int to,next;
}edge[maxn];
int cnt=1,head[maxn],n,m;
void add(int u,int v)
{
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
} 
int book[maxn],match[maxn];
bool find(int x)
{
	for(int i=head[x];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(!book[v])
		{
			book[v]=1;
			if(match[v]==0||find(match[v]))
			{
				match[v]=x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	int n1,n2,m;
	scanf("%d%d%d",&n1,&n2,&m);
	for(int i=0;i<m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	int ans=0;
	for(int i=1;i<=n1;i++)
	{
		memset(book,0,sizeof book);
		if(find(i))
			ans++;
	}
	printf("%d",ans);
	return 0;
}