Asteroids

http://poj.org/problem?id=3041

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int MAXN=;

 int n,k;

 bool use[MAXN];

 int from[MAXN],ans;

 vector<int>g[MAXN];

 bool match(int x)

 {

     for(int i=;i<g[x].size();i++)

     {

         if(!use[g[x][i]]){

             use[g[x][i]]=true;

             if(from[g[x][i]]==-||match(from[g[x][i]])){

                 from[g[x][i]]=x;

                 return true;

             }

         }

     }

     return false;

 }

 int hun()

 {

     ans=;

     memset(from,,sizeof(from));

     for(int i=; i<=n; i++)

     {

         memset(use,false,sizeof(use));

         if(match(i))

         ans++;

     }

     return ans;

 }

 int main()

 {

     int a,b;

    while(scanf("%d%d",&n,&k)!=EOF){

     for(int i=;i<=k;i++)

     {

         scanf("%d%d",&a,&b);

         g[a].push_back(b);

     }

     printf("%d\n",hun());

    }

     return ;

 }

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int MAXN=;

 int n,k;

 bool use[MAXN];

 int match[MAXN],ans;

 int g[MAXN][MAXN];

 bool dfs(int x)

 {

     for(int i=;i<=n;i++)

     {

         if(!use[i]&&g[x][i]){

             use[i]=true;

             if(match[i]==-||dfs(match[i])){

                 match[i]=x;

                 return true;

             }

         }

     }

     return false;

 }

 int hun()

 {

     ans=;

     memset(match,-,sizeof(match));

     for(int i=; i<=n; i++)

     {

         memset(use,false,sizeof(use));

         if(dfs(i))

         ans++;

     }

     return ans;

 }

 int main()

 {

     int a,b;

     while(scanf("%d%d",&n,&k)!=EOF)

     {

         memset(g,,sizeof(g));

         for(int i=; i<=k; i++)

         {

             scanf("%d%d",&a,&b);

              g[a][b]=;

         }

         printf("%d\n",hun());

     }

     return ;

 }