Pagini recente » Cod sursa (job #2608585) | Cod sursa (job #1367694) | Cod sursa (job #66233) | Cod sursa (job #403154) | Cod sursa (job #984399)
Cod sursa(job #984399)
#include <algorithm>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
#define nod1 first
#define nod2 second
typedef pair<int,int> Pair;
#define IT(type) vector<type>::iterator
#define LT(type) list<type>::iterator
ifstream F("ciclueuler.in");
ofstream G("ciclueuler.out");
const int Nmax = 100010;
const int Mmax = 500010;
Pair Edge[Mmax];
int N,M,Grad[Nmax];
list<int> V[Nmax];
LT(int) it[Nmax];
int Mark[Mmax];
int Good_graph()
{
for (int i=1;i<=N;++i)
if ( Grad[i] % 2 == 1 )
return 0;
return 1;
}
vector<int> cycle;
void Make_cycle(int nod)
{
for (it[nod]=V[nod].begin();it[nod]!=V[nod].end();++it[nod])
if ( Mark[*it[nod]] == 0 )
{
Mark[*it[nod]] = 1;
int where = Edge[*it[nod]].nod1 + Edge[*it[nod]].nod2 - nod;
Make_cycle( where );
}
cycle.push_back( nod );
}
int main()
{
F>>N>>M;
for (int i=1;i<=M;++i)
{
F>>Edge[i].nod1>>Edge[i].nod2;
V[ Edge[i].nod1 ].push_back( i );
V[ Edge[i].nod2 ].push_back( i );
Grad[Edge[i].nod1]++;
Grad[Edge[i].nod2]++;
}
if ( Good_graph() == 0 )
{
G<<"-1\n";
return 0;
}
Make_cycle(1);
reverse(cycle.begin(),cycle.end());
for (unsigned int i=0;i<cycle.size()-1;++i)
G<<cycle[i]<<' ';
G<<'\n';
}