Pagini recente » Cod sursa (job #2128785) | Cod sursa (job #1978600) | Monitorul de evaluare | Rating Dobrescu Diana (Diana523) | Cod sursa (job #972007)
Cod sursa(job #972007)
#include<fstream>
#include<algorithm>
#include<stack>
#include<vector>
#define NMAX 100005
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
vector < int > G[NMAX] , Sol;
stack < int > S;
int N,M,degree[NMAX],numb;
bool used[NMAX];
void DepthFirstSearch ( int node )
{
used [node] = true ;
++numb;
for( vector < int > :: iterator it=G[node].begin () ; it != G[node].end() ; ++it )
if( ! used[*it] )
DepthFirstSearch(*it);
}
bool Check_Euler ( void )
{
DepthFirstSearch(1);
if( numb !=N )
return 1;
for( int i(1); i <= N ; ++i )
if( G[i].size() %2 )
return 1;
return 0;
}
void Delete ( int father , int node )
{
G[father].erase(G[father].begin());
for( vector < int> :: iterator it=G[node].begin () ; it != G[node].end() ; ++it)
if( *it == father )
{
G[node].erase(it);
return ;
}
}
void Euler ( int node )
{
int newnode;
while( G[node].size() )
{
newnode=G[node].front();
S.push(node);
Delete(node,newnode);
node=newnode;
}
}
void Solve ( void )
{
int node;
if( Check_Euler())
{
g<<-1<<"\n";
g.close();
return ;
}
node=1;
do
{
Euler(node);
node=S.top();
S.pop();
Sol.push_back(node);
}while(!S.empty());
}
void Write ( void )
{
for( vector< int> :: iterator it =Sol.end() -1; it != Sol.begin() -1 ; --it )
g<<*it<<" ";
g.close();
}
int main ( void )
{
f>>N>>M;
for(int i(1) ; i <= M ; ++i )
{
int x,y;
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
f.close();
Solve();
Write();
return 0 ;
}