Pagini recente » Cod sursa (job #2085502) | Cod sursa (job #705965) | Cod sursa (job #202282) | Cod sursa (job #2178540) | Cod sursa (job #409097)
Cod sursa(job #409097)
#include <algorithm>
#include <bitset>
#include <stack>
#include <vector>
using namespace std;
#define MAX_N 100005
#define MAX_S 10005
char s[ MAX_S ];
int N, M;
int cnt_s, g[ MAX_N ];
bitset <MAX_N> f;
stack <int> stv;
vector <int> sol, v[ MAX_N ];
void df( const int &nod ) {
vector <int> :: iterator it;
f[ nod ] = true;
for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
if( f[ *it ] == false )
df( *it );
}
void rem( const int &x, const int &y ) {
vector <int> :: iterator it;
for( it = v[ x ].begin(); it != v[ x ].end(); ++it )
if( *it == y ) {
*it = v[ x ][ v[ x ].size() - 1 ];
v[ x ].pop_back();
break;
}
}
void euler( int nod ) {
int aux;
while( true ) {
if( v[ nod ].empty() )
break;
aux = v[ nod ].back();
stv.push( aux );
rem( nod, aux );
rem( aux, nod );
nod = aux;
}
}
void read( int &val ) {
while( !isdigit( s[ cnt_s ] ) )
if( ++cnt_s == MAX_S ) {
fread( s, 1, MAX_S, stdin );
cnt_s = 0;
}
val = 0;
while( isdigit( s[ cnt_s ] ) ) {
val = val*10 + s[ cnt_s ] - '0';
if( ++cnt_s == MAX_S ) {
fread( s, 1, MAX_S, stdin );
cnt_s = 0;
}
}
}
int main() {
freopen( "ciclueuler.in", "r", stdin );
freopen( "ciclueuler.out", "w", stdout );
int i, x, y, nod;
vector <int> :: iterator it;
cnt_s = MAX_S - 1;
read( N );
read( M );
while( M-- ) {
read( x );
read( y );
++g[ x ];
++g[ y ];
v[ x ].push_back( y );
v[ y ].push_back( x );
}
for( i = 1; i <= N; ++i )
if( g[ i ] & 1 ) {
printf( "-1" );
return 0;
}
df( 1 );
for( i = 1; i <= N; ++i )
if( f[ i ] == false ) {
printf( "-1" );
return 0;
}
nod = 1;
do {
euler( nod );
nod = stv.top();
stv.pop();
sol.push_back( nod );
}
while( !stv.empty() );
for( it = sol.begin(); it != sol.end(); ++it )
printf( "%d ", *it );
return 0;
}