Pagini recente » Cod sursa (job #2430981) | Cod sursa (job #1147918) | Cod sursa (job #1892329) | Cod sursa (job #3188141) | Cod sursa (job #1757207)
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <map>
using namespace std;
#define Nmax 100002
ifstream fin( "ciclueuler.in" );
ofstream fout( "ciclueuler.out" );
int N, M, Grad[Nmax];
vector < int > G[Nmax], Sol;
bitset < Nmax > Viz;
map < pair<int,int>, int > NrEdg;
void DFSEu( int nod ){
vector < int > :: iterator it;
for( it = G[nod].begin(); it != G[nod].end(); ++it ){
if( NrEdg[{nod,*it}] > 0 ){
NrEdg[{nod,*it}]--;
NrEdg[{*it,nod}]--;
DFSEu( *it );
}
}
Sol.push_back( nod );
}
int vz = 0;
void DFS( int nod ){
vz++;
Viz[nod] = 1;
vector < int > :: iterator it;
for( it = G[nod].begin(); it != G[nod].end(); ++it )
if( !Viz[*it] )
DFS(*it);
}
bool Eulerian(){
for( int i = 1; i <= N; ++i )
if( Grad[i] & 1 )
return 0;
DFS(1);
if( vz < N )
return 0;
return 1;
}
inline void AddEdge( int x, int y ){
G[x].push_back(y);
G[y].push_back(x);
Grad[x]++;
Grad[y]++;
NrEdg[{x,y}]++;
NrEdg[{y,x}]++;
}
int main(){
int x, y;
fin >> N >> M;
while( M-- ){
fin >> x >> y;
AddEdge(x,y);
}
if( !Eulerian() ){
fout << -1;
return 0;
}
DFSEu(1);
Sol.pop_back();
vector < int > :: iterator it;
for( it = Sol.begin(); it != Sol.end(); ++it )
fout << *it << " ";
return 0;
}