Pagini recente » Cod sursa (job #2353579) | Cod sursa (job #1165985) | Cod sursa (job #1063968) | Cod sursa (job #2267013) | Cod sursa (job #1130240)
#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;
typedef vector < int > ::iterator vii;
ifstream in ( "ciclueuler.in" );
ofstream out ( "ciclueuler.out" );
stack < int > S;
vector < int > G[NMAX] , Sol ;
int N , M , Nr_Nodes;
bool used[NMAX];
void DepthFirstSearch ( int node )
{
used[node] = true;
++Nr_Nodes;
for ( vii it = G[node].begin() ; it != G[node].end() ; ++it )
if ( !used[*it] )
DepthFirstSearch ( *it );
}
bool CheckEuler ( void )
{
int i ;
DepthFirstSearch ( 1 );
if ( Nr_Nodes != N ) return 1;
for ( i = 1 ; i <= N ; ++i )
if ( G[i].size() % 2 )
return 1 ;
return 0 ;
}
void DeleteEdge ( int X , int Y )
{
for ( vii it = G[X].begin() ; it != G[X].end() ; ++it )
if ( *it == Y )
{
G[X].erase( it );
return ;
}
}
void Euler ( int node )
{
int newnode;
while ( G[node].size() )
{
newnode = G[node].front();
S.push(node);
DeleteEdge ( 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 ( CheckEuler() )
out << "-1\n" ;
else
{
int node = 1;
do
{
Euler ( node );
node = S.top() ; S.pop();
Sol.push_back(node);
}while ( !S.empty() );
}
reverse ( Sol.begin() , Sol.end() );
for ( vii it = Sol.begin() ; it != Sol.end() ; ++it )
out <<*it << " ";
in.close();
out.close();
return 0 ;
}