Pagini recente » Borderou de evaluare (job #2752160) | Borderou de evaluare (job #1969268) | Borderou de evaluare (job #128933) | Cod sursa (job #460750)
Cod sursa(job #460750)
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>
#define Nmax 100111
/*
*
*/
using namespace std;
int d[Nmax];
vector< int > S, r;
vector< int > G[Nmax];
vector< int >::iterator it, iend;
inline void DFS( int x )
{
int w;
while( !G[x].empty() )
{
it=G[x].begin();
w=*it;
G[x].erase(it);
G[w].erase( find( G[w].begin(), G[w].end(), x ) );
S.push_back(x);
x=w;
}
}
inline bool IsNC( int N )
{
int x, j=1;
vector< bool > uz( N+1 );
uz[1]=true;
for( S.push_back(1); !S.empty(); )
{
x=S.back(); S.pop_back();
for( it=G[x].begin(), iend=G[x].end(); it < iend; ++it )
if( false == uz[*it] )
{
S.push_back(*it);
++j;
if( N == j )
{
S.clear();
return false;
}
}
}
return true;
}
int main( void )
{
int N, M, x, y;
ifstream in( "ciclueuler.in" );
ofstream out( "ciclueuler.out" );
for( in>>N>>M; M; --M )
{
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
++d[x]; ++d[y];
}
for( x=1; x <= N; ++x )
if( d[x]%2 )
{
out<<"-1";
return EXIT_SUCCESS;
}
if( IsNC(N) )
{
out<<"-1";
return EXIT_SUCCESS;
}
x=1;
do
{
DFS(x);
x=S.back(); S.pop_back();
r.push_back(x);
}while( !S.empty() );
copy( r.rbegin(), r.rend(), ostream_iterator<int>( out, " " ) );
out<<'\n';
return EXIT_SUCCESS;
}