Pagini recente » Cod sursa (job #1959188) | Cod sursa (job #2851805) | Cod sursa (job #603720) | Cod sursa (job #990681) | Cod sursa (job #990193)
Cod sursa(job #990193)
#include<fstream>
#include<cstring>
using namespace std;
typedef struct celula{
int nod;
celula *next;
}*lista;
lista graf[8200],v;
int i,n,m,x,y,l[8200],r[8200];
bool viz[8200];
bool cupleaza(int nod) {
if(viz[nod]==1) return 0;
viz[nod]=1;
for(lista p=graf[nod]; p; p=p->next)
if(!r[p->nod]){
l[nod]=p->nod;
r[p->nod]=nod;
return 1;
}
for(lista p=graf[nod]; p; p=p->next)
if(cupleaza(r[p->nod])) {
l[nod]=p->nod;
r[p->nod]=nod;
return 1;
}
return 0;
}
int main(void) {
ifstream fin("felinare.in");
ofstream fout("felinare.out");
fin>>n>>m;
for (i=1; i<=m; ++i) {
fin>>x>>y;
v=new celula; v->nod=y; v->next=graf[x]; graf[x]=v;
}
bool ok=1;
while (ok) {
ok=0; memset(viz,0,sizeof(viz));
for (i=1; i<=n; ++i)
if (l[i]==0) ok|=cupleaza(i);
}
int cuplaj=0;
for (i=1; i<=n; ++i)
if (l[i]>0) ++cuplaj;
fout<<2*n-cuplaj;
return(0);
}