Pagini recente » Cod sursa (job #2414336) | Cod sursa (job #2587294) | Cod sursa (job #3171612) | Cod sursa (job #715695) | Cod sursa (job #1753730)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <iterator>
#include <queue>
#include <stack>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n,m;
vector <int> adjList[100000];
queue <int> path;
stack <int> S;
int nrEdge[100000];
int check()
{
for(int i=1;i<=n;i++)
if(nrEdge[i]%2==1 || nrEdge[i]==0)
return 0;
return 1;
}
void deleteEgde(int v,int w)
{
adjList[v].pop_back();
for(vector<int>::iterator it=adjList[w].begin();it!=adjList[w].end();it++)
if(*it==v)
{
adjList[w].erase(it);
break;
}
}
void EulerianCycle()
{
int w,v;
while(!S.empty()){
v=S.top();S.pop();
while(!adjList[v].empty())
{
w=adjList[v].back();
deleteEgde(v,w);
S.push(w);
v=w;
}
path.push(v);
}
}
int main()
{
f >> n >> m;
int x,y;
for(int i=0;i<m;i++){
f >> x >> y;
adjList[x].push_back(y); nrEdge[x]++;
adjList[y].push_back(x); nrEdge[y]++;
}
if(check()==1){
S.push(1);
EulerianCycle();
path.pop();
while(!path.empty())
{
g << path.front() << " ";
path.pop();
}
}else g << "-1";
return 0;
}