Cod sursa(job #990193)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 27 august 2013 17:30:59
Problema Felinare Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#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);
}