Pagini recente » Cod sursa (job #1284403) | Cod sursa (job #1438874) | Cod sursa (job #1115329) | Cod sursa (job #243690) | Cod sursa (job #1409837)
#include <fstream>
#include <list>
#include <vector>
#include <stack>
using namespace std;
long n, m;
list<long> *graf;
vector<long> ciclu;
bool isEuler()
{
for(long i=1; i<=n; ++i)
if(graf[i].size()%2==1||graf[i].size()==0) return false;
return true;
}
void buildEuler()
{
long a, b;
stack<long> s;
s.push(1);
while(!s.empty())
{
a=s.top();
if(graf[a].size())
{
b=graf[a].front();
for(list<long>::iterator it=graf[b].begin(), ed=graf[b].end(); it!=ed; ++it)
if(*it==a)
{
graf[b].erase(it);
break;
}
graf[a].pop_front();
s.push(b);
}
else
{
ciclu.push_back(a);
s.pop();
}
}
}
int main()
{
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
long a, b;
in>>n>>m;
graf = new list<long>[n+1];
for(long i=0; i<m; ++i)
{
in>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);
}
if(isEuler())
{
buildEuler();
for(vector<long>::iterator it=ciclu.begin(), ed=ciclu.end(); it!=ed; ++it)
out<<*it<<' ';
}
else
out<<"-1\n";
return 0;
}