Pagini recente » arena | Istoria paginii runda/oji2018 | Cod sursa (job #600901) | Istoria paginii runda/ason/clasament | Cod sursa (job #2118797)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int MAX = 500005;
bool beenThere[MAX];
vector < pair < int , int > > myVector[MAX];
int Grad[MAX];
stack < int > myStack;
vector < int > Answer;
int N, M;
void Read()
{
in >> N >> M;
for ( int i = 1; i <= M ; ++i)
{
int x,y;
in >> x >> y;
myVector[x].push_back(make_pair(y,i));
myVector[y].push_back(make_pair(x,i));
Grad[x]++;
Grad[y]++;
}
}
void Rezolv()
{
for ( int i = 1; i <= N ; ++i)
if(Grad[i]&1 || Grad[i] == 0)
{
out << -1;
return;
}
myStack.push(1);
while(!myStack.empty())
{
int nodCurent = myStack.top();
if(myVector[nodCurent].size() > 0)
{
int x = myVector[nodCurent].back().first;
int edge = myVector[nodCurent].back().second;
myVector[nodCurent].pop_back();
if(!beenThere[edge])
{
beenThere[edge] = true;
myStack.push(x);
}
}
else
{
myStack.pop();
Answer.push_back(nodCurent);
}
}
for ( int i = 0 ; i < Answer.size()-1 ; ++i) out << Answer[i] <<" ";
}
int main()
{
Read();
Rezolv();
}