Cod sursa(job #3195752)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 21 ianuarie 2024 16:41:07
Problema Felinare Scor 2
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#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;
}