423 Promo

[•DITzoneC]

Aici puteţi discuta despre problema Promo.

[•Bogdan_tmm]

O prima intrebare:
Raspunsul acesta e bun?

Cod:

15
7 8
4 5
10 11
8 9
5 6
12 13
9 7
6 4
14 15
1 2
2 3

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

[•pauldb]

Ce legatura au componentele tare-conexe cu aceasta problema? Graful nu e nici macar orientat.

[•alexandru92]

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;
}

[•mihai_florea]

Se pare ca problema Promo nu mai are nume in monitorul de evaluare 

[•costyv87]

Putem gasi undeva testele de la problema asta? Chiar vreau sa imi verific solutia si nu le gasesc. Daca se poate , va rog, sa imi dati macar un test.