Pagini recente » Cod sursa (job #2167277) | Cod sursa (job #1204113) | Cod sursa (job #1943171) | Cod sursa (job #1116599) | Cod sursa (job #1613039)
#include <fstream>
#include <vector>
#include <iostream>
#define DIM 8200
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
int N,M,nr,ok,felinare;
vector <int> L[DIM],r(DIM),l(DIM),v(DIM),ans(DIM);
int cuplaj(int nod){
v[nod]=1;
for(int i=0;i<L[nod].size();i++)
if(r[L[nod][i]]==0){
r[L[nod][i]]=nod;
l[nod] = L[nod][i];
return 1;
}
for(int i=0;i<L[nod].size();i++)
if(v[r[L[nod][i]]]==0 && cuplaj(r[L[nod][i]])){
l[nod] = L[nod][i];
r[L[nod][i]] = nod;
return 1;
}
return 0;
}
int main(){
fin >> N >> M;
while(M--){
int x,y;
fin >> x >> y;
L[x].push_back(y);
}
do{
ok=0;
for(int i=1;i<=N;i++)
v[i]=0;
for(int i=1;i<=N;i++)
if(!l[i] && cuplaj(i)){
nr++;
ok=1;
}
}while(ok);
for(int i=1;i<=N;i++){
if(l[i] && !r[i])
felinare+=2;
if(!l[i] && !r[i])
felinare+=2;
if(!l[i] && r[i])
felinare+=2;
}
fout << felinare << "\n";
}