题解 | #炸弹#

将每个点定义为二分图中的一条边，此时每条边都需要被他的任意一个端点覆盖，就变成了最小点覆盖问题。
而最小点覆盖=最大匹配
套匈牙利算法模板就好啦

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+10;
int st[N],match[N];
int g[1005][1005];
int n,k;
bool find(int u)
{
	for(int i=1;i<=n;i++)
	{
		if(st[i])
		{
			continue;
		}
		if(g[u][i])
		{
			st[i]=true;
			if(match[i] == -1 || find(match[i]))
			{
				match[i]=u;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	memset(match,-1,sizeof match);
	cin>>n>>k;
	for(int i=0;i<k;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x][y]=1;
	}
	int res=0;
	for(int i=1;i<=n;i++)
	{
		memset(st,false,sizeof st);
		if(find(i))
		{
			res++;
		}
	}
	cout<<res;
}