Pagini recente » Cod sursa (job #1919242) | Cod sursa (job #2701200) | Cod sursa (job #2518730) | Cod sursa (job #2049585) | Cod sursa (job #522616)
Cod sursa(job #522616)
#include <cstdio>
#include <vector>
#include <stack>
#include <utility>
using namespace std;
int n,m;
vector<pair<int,int> > V[1<<17];
int ind[1<<17];
vector<int> ciclu;
stack<int> ST;
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf ("%d%d",&n,&m);
for (int i=0;i<m;i++)
{
int a,b;
scanf ("%d%d",&a,&b);
ind[a]++;ind[b]++;
if (a == b)
{
V[a].push_back(make_pair(a,V[a].size()+1));
V[a].push_back(make_pair(a,V[a].size()-1));
}
else
{
V[a].push_back(make_pair(b,V[b].size()));
V[b].push_back(make_pair(a,V[a].size()-1));
}
}
for (int i=1;i<=n;i++)
if (ind[i]&1)
{
printf ("-1\n");
return 0;
}
ST.push(1);
while (ST.size() > 0)
{
int node = ST.top();
while (V[node].size() > 0 && V[node].back().first < 0) V[node].pop_back();
if (V[node].size() > 0)
{
pair<int,int> much = V[node].back();
ST.push(much.first);
V[much.first][much.second].first = -1;
ind[node]--;
ind[much.first]--;
V[node].pop_back();
}
else
{
ciclu.push_back(node);
ind[node] = -1;
ST.pop();
}
}
for (int i=1;i<=n;i++)
if (ind[i] != -1)
{
printf ("-1\n");
return 0;
}
for (size_t i=0;i<ciclu.size()-1;i++)
printf ("%d ",ciclu[i]);
printf ("\n");
return 0;
}