Pagini recente » Borderou de evaluare (job #951726) | Cod sursa (job #765749)
Cod sursa(job #765749)
#include<iostream>
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
struct nod {
int y,m;
inline nod(int _y, int _m) {
y=_y;
m=_m;
}
};
struct stiva {
int x;
vector <nod> :: iterator it;
};
vector <nod> v[100001];
int gr[100001],s[500001];
bitset <500001> d;
stiva st[500001];
ofstream g("ciclueuler.out");
inline void dfs(int x)
{
int l,aux;
vector <nod> :: iterator it;
l=1;
st[1].x=x;
st[1].it=v[x].begin();
while(l>=1) {
aux=l;
for(it=st[l].it;it!=v[st[l].x].end();it++)
if(d[it->m]==0) {
d[it->m]=1;
s[l]=st[l].x;
st[l].it=it;
l++;
st[l].x=it->y;
st[l].it=v[it->y].begin();
break;
}
if(aux==l) {
l--;
if(l)
g<<s[l]<<" ";
}
}
}
int main ()
{
int n,m,i,x,y,c;
ifstream f("ciclueuler.in");
f>>n>>m;
for(i=1;i<=m;i++) {
f>>x>>y;
v[x].push_back(nod(y,i));
v[y].push_back(nod(x,i));
gr[x]++;
gr[y]++;
}
f.close();
c=1;
for(i=1;i<=n;i++)
if(gr[i]%2==1) {
c=0;
break;
}
if(c==0)
g<<"-1";
else dfs(1);
g.close();
return 0;
}