POJ 3041 Asteroids (最小顶点覆盖)_最小顶点覆盖 贪心反例

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
 
using namespace std;
 
const int maxn = 500 + 10;
 
vector<int>E[maxn];
bool vis[maxn];
int y[maxn];
 
bool dfs(int u) {
	for( int i=0; i<E[u].size(); i++ ) {
		int v = E[u][i];
		if(vis[v]) continue;
		vis[v] = true;
		if(y[v] == 0 || dfs(y[v])) {
			//printf("u = %d v = %d y[v] = %d\n", u, v, y[v]);
			y[v] = u;
			return true;
		}
	}
	return false;
}
 
int main() {
	freopen("in", "r", stdin);
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF) {
		for( int i=1; i<=n; i++ ) E[i].clear();
		for( int i=0; i<m; i++ ) {
			int u, v;
			scanf("%d%d", &u, &v);
			E[u].push_back(v);
		}
		int ans = 0;
		memset(y, 0, sizeof(y));
		for( int i=1; i<=n; i++ ) {
			memset(vis, 0, sizeof(vis));
			if(dfs(i)) ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}