Pagini recente » Statistici Rotaru Oana-Dumitrita (Rotaru-Oana) | Cod sursa (job #2790863) | Cod sursa (job #1547490) | Cod sursa (job #441875) | Cod sursa (job #1778682)
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#define NX 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n,m,p;
int deg[NX], viz[NX];
vector<int> v[NX];
queue<int> Q;
stack<int> S;
void citeste()
{
int x,y;
fin>>n>>m;
while(m--)
{
fin>>x>>y;
v[y].push_back(x);deg[y]++;
v[x].push_back(y);deg[x]++;
}
}
void BFS()
{
int a;
viz[1]=1;
Q.push(1);
while(!Q.empty())
{
a=Q.front();
for(auto it=v[a].begin(); it!=v[a].end();it++)
if(viz[*it]==0)
{
viz[*it]=1;
Q.push(*it);
}
Q.pop();
}
}
int conex()
{
BFS();
for(int i=1;i<=n;i++)
if(viz[i]==0)
return 0;
return 1;
}
int este_euclid()
{
if(!conex())
return 0;
for(int i=1;i<=n;i++)
if(deg[i]%2==1)
return 0;
return 1;
}
void euler(int p)
{
int w;
while(!v[p].empty())
{
w=v[p].back();
v[p].pop_back();
for(auto it=v[w].begin(); it!=v[w].end();it++)
if(*it==p)
{
v[w].erase(it,it+1);
break;
}
euler(w);
}
S.push(p);
}
int rezultat()
{
if(este_euclid()==0)
return -1;
euler(1);
return 1;
}
int main()
{
citeste();
if(rezultat()==-1){
fout<<-1;
}
else{
while(!S.empty())
{
deg[++deg[0]]=S.top();
S.pop();
}
for(int i=1;i<deg[0];i++){
fout<<deg[i];
if(i<deg[0]-1)
fout<<' ';
}
}
return 0;
}