Cod sursa(job #864819)

Utilizator veleanduAlex Velea veleandu Data 25 ianuarie 2013 19:25:56
Problema Felinare Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cassert>
#include <cstdio>       

#include <vector>

using namespace std;

	#define max_n 10000
	#define pb push_back 

int St[ max_n ],Dr[ max_n ];
bool Viz[ max_n ];
int n;

vector<int> Vertex[ max_n ];

bool find_path ( int nod ){
	if ( Viz[ nod ] )
		return 0;
	Viz[ nod ] = 1;
	for ( int i=0; i< Vertex[ nod ].size(); ++i ){
		if ( !Dr[ Vertex[ nod ][ i ] ] || find_path ( Dr[ Vertex[ nod ][ i ] ] ) ){
			St[ nod ] = Vertex[ nod ][ i ];
			Dr[ Vertex[ nod ][ i ] ] = nod;
			return 1;
		}
	}
	return 0;
}

int main(){

    freopen ("felinare.in","r",stdin);
	freopen ("felinare.out","w",stdout);

	int m;
	int a,b;
	scanf ("%d %d", &n, &m );
	for ( ; m; --m ){
		scanf ("%d %d", &a, &b );
		Vertex[ a ]. pb ( b );
	}

    bool ok;
	int rez=0;
	do {
		ok = false;
		for ( int i=1; i<=n; ++i ){
			if ( !St[ i ] ){
            	ok = find_path ( i );
				rez += ok;
			}
		}
		for ( int i=1; i<=n; ++i )
			Viz[ i ] = false ;
	} while ( ok );

	printf("%d\n",2*n-rez);

	return 0;
}