Imprimă pagina - 423 Promo

O prima intrebare:
Raspunsul acesta e bun?

Cod:

Eu determin componentele tari conexe si dupa e destul de usor de rezolvat, dar iau 0 :D
De ce nu ar merge cum zic?Macar un test sa fi prins

Imi puteti spune unde gresesc.
Eu determin fiecare componenta conexa apoi pentru fiecare nod din componenta ii atribui un numar comun si un numar care difera.
Ca sa ma asigur ca atribui numere din intervalul [ 1, 2*m+1 ) retin valorile intr-un vector in care elementele sunt in oridine inversa.

Cod:

#include <vector>
#include <utility>
#include <fstream>
#include <cassert>

/*
 * 
 */
using namespace std;
vector< bool > uz;
vector< pair< int, int > > offer;
vector< int > cconex, element;
vector< vector< int > > v;
vector< int >::const_iterator it, iend;
void DFS( int x )
{
	vector< int >::const_iterator it=v[x].begin(), iend=v[x].end();
	uz[x]=true;
	cconex.push_back(x);
	for( ; it < iend; ++it )
		if( !uz[*it] )
			DFS( *it );
}
int main()
{int m, k, common, i, x, y;
	ifstream in( "promo.in");
	in>>m>>k;
	v.resize(m);
	for( ; k; --k )
	{
		in>>x>>y;
		x-=1;
		y-=1;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	element.push_back( 2*m+1 );
	for( k=2*m; k > 0; --k )
		element.push_back(k);
	uz.resize(m);
	offer.resize(m);
	for( k=0;  k < m; ++k )
		if( !uz[k] )
		{
			DFS( k );
			common=element.back();
			element.pop_back();
			assert( !element.empty() );
			for( it=cconex.begin(), iend=cconex.end(); it < iend; ++it )
			{
				offer[*it]=make_pair< int, int>( common, element.back() );
				element.pop_back();
				assert( !element.empty() );
			}
			cconex.clear();
		}
	ofstream out("promo.out");
	out<<(element.back()-1)<<'\n';
	for( i=0; i < m; ++i )
		out<<offer[i].first<<' '<<offer[i].second<<'\n';
	return 0;
}

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Aprilie 24, 2007, 07:50:26