Cod sursa(job #2340936)

Utilizator aditzu7Adrian Capraru aditzu7 Data 11 februarie 2019 12:20:01
Problema Felinare Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

vector <int> v[20005];
int ok,viz[20005];
int i,x,y,n,m,w,dr[10005],st[10005];
int pairup(int nod){
int i,vec;
if(viz[nod]) return 0;
viz[nod]=1;
for(i=0;i<v[nod].size();i++){
    vec=v[nod][i];
    if(!dr[vec]){
        dr[vec]=nod;
        st[nod]=vec;
        return 1;
    }


}
for(i=0;i<v[nod].size();i++){
    vec=v[nod][i];
    if(pairup(dr[vec])){
        dr[vec]=nod;
        st[nod]=vec;
        return 1;
    }

}
return 0;
}

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",&x,&y);
        v[x].push_back(y);
       // v[y].push_back(x);


    }
    ok=1;
    while(ok){
        ok=0;
        memset(viz,0,sizeof(viz));
        for(i=1;i<=n;i++)
            if(!st[i]) ok|=pairup(i);


    }int ss=0;

for(i=1;i<=n;i++) if(st[i]) ss++;

printf("%d\n",2*n-ss);
//for(i=1;i<=m;i++) if(st[i]) printf("%d %d\n",st[i],i);
   return 0;
}