【POJ 3041】Asteroids (最小点覆盖)

#include <cstdio>
#include <cstring>
const int N=505;
int n,vis[N],link[N],g[N][N];
int find(int u){
    for(int i=1; i<=n; i++)//这个1~n是v的范围
        if(g[u][i]&&!vis[i]){
            vis[i]=1;
            if(!link[i]||find(link[i])){
                link[i]=u;
                return 1;
            }
        }
    return 0;
}
int solve(){
    memset(link,0,sizeof link);
    int ans=0;
    for(int i=1;i<=n;i++){//这个1~n是u的范围
        memset(vis,0,sizeof vis);
        if(find(i))ans++;
    }
    return ans;
}
int main(){
    int m,u,v;
    scanf("%d%d",&n,&m);
    memset(g,0,sizeof g);
    while(m--){
        scanf("%d%d",&u,&v);
        g[u][v]=1;
    }
    printf("%d\n",solve());
}