Pagini recente » Cod sursa (job #3265607) | Cod sursa (job #2872159) | Cod sursa (job #2604724) | Cod sursa (job #2669974) | Cod sursa (job #3195752)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ( "felinare.in" );
ofstream fout ( "felinare.out" );
const int N = 1e4;
vector <int> g[N];
int l[N], r[N], viz[N];
int PairUp ( int n ) {
if ( viz[n] != 0 )
return 0;
viz[n] = 1;
for ( int i = 0; i < g[n].size(); i++ ) {
if ( r[g[n][i]] == 0 ) {
l[n] = g[n][i];
r[g[n][i]] = n;
return 1;
}
}
for ( int i = 0; i < g[n].size(); i++ ) {
if ( PairUp (g[n][i]) == 1 ) {
l[n] = g[n][i];
r[g[n][i]] = n;
return 1;
}
}
return 0;
}
int main () {
int n, m, a, b;
fin >> n >> m;
for ( int i = 0; i < m; i++ ) {
fin >> a >> b;
g[a].push_back (b);
}
int ok = 1;
while ( ok == 1 ) {
ok = 0;
for ( int i = 1; i <= n; i++ )
viz[i] = 0;
for ( int i = 1; i <= n; i++ ) {
if ( l[i] == 0 && PairUp(i) == 1 )
ok = 1;
}
}
int cnt = 0;
for ( int i = 1; i <= n; i++ )
if ( l[i] != 0 )
cnt++;
fout << 2 * n - cnt << "\n";
return 0;
}