POJ3041(最大顶点覆盖)

#include"cstdio"
#include"cstring"
#include"vector"
using namespace std;
const int MAXN=500;
vector<int> G[MAXN*2+10];
int N,K;
void add_edge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}
int match[MAXN*2+10];
bool vis[MAXN];
bool dfs(int u)
{
    vis[u]=true;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i],w=match[v];
        if(w<0||(!vis[w]&&dfs(w)))
        {
            match[u]=v;
            match[v]=u;
            return true;    
        }
    }
    return false;
}
int bipartite_matching()
{
    int ans=0;
    memset(match,-1,sizeof(match));
    for(int i=1;i<=N;i++)
    {
        if(match[i]<0)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i))    ans++;
        }
    }
    return ans;
}
int main()
{
    while(scanf("%d%d",&N,&K)!=EOF)
    {
        for(int i=0;i<=2*MAXN;i++)    G[i].clear();
        for(int i=0;i<K;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(u,v+MAXN);    
        }
        
        int ans=bipartite_matching();
        printf("%d\n",ans);
    }
    return 0;
}