Pagini recente » Cod sursa (job #2080319) | Cod sursa (job #2047076) | Cod sursa (job #386554) | Cod sursa (job #496593) | Cod sursa (job #2374925)
#include <bits/stdc++.h>
using namespace std;
const int nmax=100001;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int grad[nmax],sol[nmax],vc[nmax],n,m,k;
typedef pair<int,int>pereche;
vector<pereche>v[nmax];
bitset<nmax>seen;
bool verif()
{
for(int i=1;i<=n;i++)
{
if(grad[i]%2!=0||grad[i]==0)
return false;
}
return true;
}
int st[nmax],nr;
void euler(int nod)
{
k++;
st[k]=nod;
if(seen[nod]==1)
{
while(k!=0&&grad[st[k]]==0)
{
nr++;
sol[nr]=st[k];
k--;
}
}
else
seen[nod]=1;
if(k>0)
{
for(int i=0;i<v[st[k]].size();i++)
if(vc[v[st[k]][i].second]==0)
{
vc[v[st[k]][i].second]=1;
grad[v[st[k]][i].first]--;
grad[st[k]]--;
euler(v[st[k]][i].first);
}
}
}
int main()
{
in>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{
in>>x>>y;
v[x].push_back({y,i});
v[y].push_back({x,i});
grad[x]++;grad[y]++;
}
if(!verif())
out<<"-1";
else
{
euler(1);
for(int i=1;i<=nr;i++)
out<<sol[i]<<" ";
}
return 0;
}