Pagini recente » Istoria paginii runda/clasele_5_6/clasament | Cod sursa (job #1223418) | Cod sursa (job #356546) | Cod sursa (job #966366) | Cod sursa (job #294585)
Cod sursa(job #294585)
#include<stdio.h>
#define N 8200
void read(),solve(),pune(),cuplaj();
struct nod{ int inf; nod *next;};
nod *vec_out[N],*paux;
int n,m,i,a,b,sol,j,ci[N],cd[N],viz[N],creste(int st),gata;
int main()
{ read();
solve();
return 0;
}
void read()
{ 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,&b); pune();}
}
void pune()
{ paux=new nod;
paux->inf=b; paux->next=vec_out[a]; vec_out[a]=paux;
}
void solve()
{ cuplaj();
}
void cuplaj()
{
gata=0;
while(!gata)
{
gata=1;
for(i=1;i<=n;i++) viz[i]=0;
for(i=1;i<=n;i++)
if(!cd[i]&&creste(i))gata=0;
}
for(i=1;i<=n;i++)if(cd[i])sol++;
printf("%d\n",2*n-sol);
}
int creste(int st)
{ nod *ppaux;
if(viz[st]) return 0;
viz[st]=1;
for(ppaux=vec_out[st];ppaux;ppaux=ppaux->next)
if(!ci[ppaux->inf]){ ci[ppaux->inf]=st; cd[st]=ppaux->inf; return 1;}
for(ppaux=vec_out[st];ppaux;ppaux=ppaux->next)
if(creste(ci[ppaux->inf])){ ci[ppaux->inf]=st; cd[st]=ppaux->inf; return 1;}
return 0;
}