C++ 解法, 执行用时: 24ms, 内存消耗: 652K, 提交时间: 2022-07-05 15:44:58

#include<bits/stdc++.h>
using namespace std;
int n, m;
bool G[505][505], vis[505];
int link[505];  // y连的 
int ans;
int dfs(int x){
	for(int i=1;i<=n;i++){
		if(!G[x][i] || vis[i]) continue;
		vis[i] = 1;
		if(link[i] == 0 || dfs(link[i])){
			link[i] = x;
			return 1;
		}
	}
	return 0;
}
void start(){
	for(int i=1;i<=n;i++){
		memset(vis, 0, sizeof(vis));
		ans += dfs(i);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
        int x, y;
		cin>>x>>y;
		G[x][y] = true;
	}
	start();
	cout<<ans<<endl;
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 19ms, 内存消耗: 12444K, 提交时间: 2023-08-09 22:14:42

#include<bits/stdc++.h>

using namespace std;
int n,m,cnt;
vector<int>e[505010];
int vis[250010],p[250010];
bool find(int x)
{
	vis[x]=cnt;
	for(auto y:e[x]){
		if(!p[y]||(vis[p[y]]!=cnt&&find(p[y]))){
			p[y]=x;
			return 1;
		}
	}
	return 0;
}
int match()
{
	int ans=0;
	for(int i=1;i<=n;i++){
		cnt++;
		if(find(i))
			ans++;
	}
	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
	}
	cout<<match()<<"\n";
	return 0;
}