Pagini recente » Cod sursa (job #1138208) | cnitv_gimnaziu_1 | Cod sursa (job #2628545) | Cod sursa (job #1860244) | Cod sursa (job #1321921)
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <vector>
using namespace std;
int N, M, x, y, o;
bool Vis[100001];
list <int> G[100001];vector <int> Sol;
queue <int> Q;
stack <int> S;
void Input();
void Conex();
bool Eulerian();
void DFS(int v);
void Delete(int x, int y);
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
Input();
if ( !Eulerian() )
{
printf("-1");
return 0;
}
o = 1;
do {
DFS(o);
o = S.top();
S.pop();
Sol.push_back(o);
} while ( !S.empty() );
for ( int i = Sol.size()-1 ; i >= 0; --i )
printf("%i ",Sol[i]);
}
void Input()
{
scanf("%i%i",&N,&M);
for ( int i = 1; i <= M; ++i )
{
scanf("%i%i",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void Conex()
{
Q.push(1); int nod;
while ( !Q.empty() )
{
nod = Q.front();
Vis[nod] = 1;
for ( const auto& v : G[nod] )
if ( !Vis[v] )
Q.push(v);
Q.pop();
}
}
bool Eulerian()
{
Conex();
for ( int i = 1; i <= N; ++i )
{
if ( G[i].size() % 2 == 1 )
return false;
if ( Vis[i] == 0 )
return false;
}
return true;
}
void DFS(int v)
{
int v2;
while ( true )
{
if ( G[v].empty() )
break;
v2 = G[v].back();
S.push(v);
Delete(v, v2);
v = v2;
}
}
void Delete(int x, int y)
{
G[x].pop_back();
for( list <int> :: iterator it = G[y].begin(); it != G[y].end(); it++ )
{
if ( *it == x )
{
G[y].erase(it);
break;
}
}
}