Cod sursa(job #127096)

Utilizator razvi9Jurca Razvan razvi9 Data 23 ianuarie 2008 13:36:30
Problema Felinare Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<stdio.h>
#include<string.h>
int n,m,a[30000][2],st[10000],dr[10000],viz[10000],nr,i;
int cupleaza(int nod)
{int i;
 if(viz[nod]) return 0;
 viz[nod]=1;
 for(i=1;i<=m;i++)
  if(a[i][0]==nod)
   if(!dr[a[i][1]] || cupleaza(dr[a[i][1]]))
    {st[nod]=a[i][1];
     dr[a[i][1]]=nod;
     return 1;}
 return 0;}

void cuplaj()
{for(i=1;i<=n;i++)
  if(!st[i])
   if(cupleaza(i)) nr++;
   else{
     memset(viz,0,sizeof(viz));
     if(cupleaza(i)) nr++;}
 }

int main()
{freopen("felinare.in","r",stdin);
 freopen("felinare.out","w",stdout);
 scanf("%d %d",&n,&m);
 for(i=1;i<=m;i++) scanf("%d %d",&a[i][0],&a[i][1]);
 cuplaj();
 printf("%d",2*n-nr);
 fclose(stdout);
 return 0;}