Pagini recente » Cod sursa (job #1277633) | Cod sursa (job #637075) | Cod sursa (job #1329366) | Cod sursa (job #2072741) | Cod sursa (job #476590)
Cod sursa(job #476590)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
vector < int > G [ 100001 ];
int deg [ 100001 ];
bitset <100001> u;
queue <int> q;
int n, m;
stack <int> c;
void bfs (){
int i, n, t;
q . push ( 1 );
u . set ( 1 );
while ( ! q . empty () ){
n = q . front ();
q . pop ();
t = G [ n ] . size ();
for ( i = 0; i < t; ++ i )
if ( ! u [ G [ n ] [ i ] ] ){
q . push ( G [ n ] [ i ] );
u . set ( G [ n ] [ i ] );
}
}
}
bool connected (){
bfs ( );
for ( int i = 1; i <= n; ++ i )
if ( ! u [ i ] && G [ i ] . size () > 0 )
return false;
return true;
}
bool eulerian (){
if ( ! connected () )
return false;
for ( int i = 1; i <= n; ++ i )
if ( deg [ i ] & 1 )
return false;
return true;
}
void euler (int n){
//cout << n << "\n";
vector < int > :: iterator i;
int e;
if ( G [ n ] . size () == 0 ){
c . push ( n );
return;
}
while ( G [ n ] . size () > 0 ){
e = G [ n ] . back ();//muchia
G [ n ] . pop_back ();
for ( i = G [ e ] . begin (); i != G [ e ] . end (); ++ i )
if ( *i == n ){
G [ e ] . erase ( i );
break;
}
euler ( e );
}
c . push ( n );
return;
}
void print ( ofstream *g ){
c.pop();
while ( ! c . empty () ){
* g << c . top () << " ";
c . pop ();
}
* g << "\n";
}
int main()
{
int i, x, y;
ifstream f ( "ciclueuler.in" );
ofstream g ( "ciclueuler.out" );
f >> n >> m;
for ( i = 0; i < m; ++ i ){
f >> x >> y;
++ deg [ x ];
++ deg [ y ];
G [ x ] . push_back ( y );
G [ y ] . push_back ( x );
}
f.close();
if ( !eulerian () ){
g << "-1\n";
g . close();
return 0;
}
else{
euler(1);
print(&g);
g . close();
}
return 0;
}