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