Pagini recente » Cod sursa (job #2939195) | Cod sursa (job #1537282) | Cod sursa (job #396216) | Cod sursa (job #3180602) | Cod sursa (job #476349)
Cod sursa(job #476349)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 100009;
vector <int> G [ MAXN ];
int deg [ MAXN ], n, m;
stack <int> cycleNode, s;
void Euler (){
int n = 1, e;
do{
if ( G [ n ] . size () == 0 ){
cycleNode . push ( n );
n = s . top ();
s . pop ();
}
else{
e = G [ n ] . back ();
G [ n ] . pop_back ();
for ( vector<int>::iterator it = G [ e ] . begin (); it != G [ e ] . end (); ++ it )
if ( * it == n ){
G [ e ] . erase ( it );
break;
}
s . push ( n );
n = e;
}
}while ( ! s . empty () );
}
int main(){
int i, x, y;
ifstream f ("ciclueuler.in");
ofstream g ("ciclueuler.out");
f >> n >> m;
while (m --){
f >> x >> y;
G [ x ] . push_back ( y );
G [ y ] . push_back ( x );
++ deg [ x ];
++ deg [ y ];
}
f . close ();
for ( i = 1; i <= n; ++ i )
if ( deg [ i ] & 1 ){
g << "-1\n";
g . close ();
return 0;
}
Euler ( );
g << "1 ";
while ( ! cycleNode . empty () ){
g << cycleNode . top () << " ";
cycleNode . pop();
}
g . close ();
return 0;
}