Pagini recente » Cod sursa (job #1910224) | Cod sursa (job #3171568) | Cod sursa (job #2035720) | Cod sursa (job #1421470) | Cod sursa (job #1377545)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#define NMAX 100005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in ( "ciclueuler.in" );
ofstream out ( "ciclueuler.out" );
bool used[NMAX] ;
vector < int > G[NMAX] , Sol;
stack < int > S ;
int N , M , number ;
void DFS ( int node ){
used[node] = true;
++number;
for ( vector < int > ::iterator it = G[node].begin () ; it != G[node].end() ; ++it )
if ( !used[node] )
DFS ( node );
}
bool EulerGraph ( void ){
int i , j ;
DFS ( 1 );
if ( number != N ) return 0;
for ( i = 1 ; i <= N ; ++i )
if ( G[i].size()&1 ) return 0 ;
return 1 ;
}
void EdgeDelete ( int X , int Y ){
G[X].erase(G[X].begin());
for (vector < int > ::iterator it = G[Y].begin () ; it != G[Y].end() ; ++it )
if( *it == X){
G[Y].erase(it);
return ;
}
}
void Euler ( int node ) {
int newnode ;
while ( G[node].size() ){
newnode = G[node].front();
S.push(node);
EdgeDelete ( node , newnode );
node = newnode;
}
}
int main ( void ){
int i , j , x, y ;
in >> N >> M ;
for ( i = 1 ; i <= M ; ++i ){
in >> x >> y ;
G[x].push_back(y) ;
G[y].push_back(x) ;
}
if ( !EulerGraph() ){
out << "-1\n";
}else{
int node = 1 ;
do {
Euler( node );
node = S.top() , S.pop();
Sol.push_back(node);
}while ( !S.empty());
}
for ( vector < int > ::iterator it = Sol.begin() ; it != Sol.end() ; ++it )
out << *it << " " ;
in.close();
out.close();
return 0 ;
}