Pagini recente » Cod sursa (job #2959447) | Cod sursa (job #2489307) | Cod sursa (job #404465) | Cod sursa (job #893427) | Cod sursa (job #1337445)
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
using namespace std;
#define Nmax 100002
FILE *f = fopen ( "ciclueuler.in", "r" );
FILE *g = fopen ( "ciclueuler.out", "w" );
vector < int > G[Nmax];
stack < int > S;
queue < int > Q;
int N, M, visited, grad[Nmax];
bool inQ[Nmax], viz[Nmax];
void BFS ( int start ){
int nod;
vector < int > :: iterator it;
Q.push( start );
inQ[start] = 1;
while ( !Q.empty() ){
nod = Q.front();
Q.pop();
viz[nod] = 1; visited++;
inQ[nod] = 0;
for ( it = G[nod].begin(); it < G[nod].end(); ++it )
if ( !viz[*it] && !inQ[*it] ){
Q.push( *it );
inQ[*it] = 1;
}
}
}
bool eulerian (){
for ( int i = 1; i <= N; ++i )
if ( grad[i] & 1 )
return 0;
return 1;
}
void sterge ( int x, int y ){
vector < int > :: iterator it;
for ( it = G[x].begin(); it < G[x].end(); ++it ){
if ( *it == y ){
G[x].erase ( it );
break;
}
}
for ( it = G[y].begin(); it < G[y].end(); ++it ){
if ( *it == x ){
G[y].erase ( it );
break;
}
}
}
void Euler ( int nod ){
vector < int > :: iterator it;
int aux;
for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
aux = *it;
sterge ( nod, aux );
Euler ( aux );
}
S.push ( nod );
}
void afisare (){
while ( S.size() > 1 ){
fprintf ( g, "%d ", S.top() );
S.pop();
}
S.pop();
}
int main(){
int x, y;
fscanf ( f, "%d%d", &N, &M );
for ( int i = 1; i <= M ;++i ){
fscanf ( f, "%d%d", &x, &y );
G[x].push_back ( y );
G[y].push_back ( x );
grad[x]++;
grad[y]++;
}
BFS ( 1 );
if ( visited == N && eulerian () ){
Euler ( 1 );
afisare ();
}
else
fprintf ( g, "-1" );
return 0;
}