Pagini recente » Cod sursa (job #439520) | Cod sursa (job #2046893) | Cod sursa (job #2958941) | Cod sursa (job #463121) | Cod sursa (job #940575)
Cod sursa(job #940575)
#include <cstdio>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <fstream>
#include <queue>
#include <stack>
#include <string.h>
#include <math.h>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=(st);i<=(dr);i+=(k))
#define ll (long long)
#define kfl(i,j) (a[(i)][(j)].c-a[(i)][(j)].f)
using namespace std;
FILE *f,*g;
list <int> a[100100];
bool bf[100100];
int gr[100100];
stack <int> S;
vector <int> sol;
int n,m;
void read()
{
int i,x,y;
f=fopen("ciclueuler.in","r");
g=fopen("ciclueuler.out","w");
fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++)
{
fscanf(f,"%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
gr[x]++;
gr[y]++;
}
}
void df(int x)
{
bf[x]=true;
for (list<int>::iterator i=a[x].begin();i!=a[x].end();i++) if (!bf[*i]) df(*i);
}
void bfs(int x)
{
queue <int> q;
q.push(x);
bf[x]=true;
while (q.size())
{
x=q.front(); q.pop();
for (list <int>::iterator i=a[x].begin();i!=a[x].end();i++)
if (!bf[*i])
{
bf[*i]=true;
q.push(*i);
}
}
}
bool pre()
{
bfs(1);
for (int i=1;i<=n;i++) if (!bf[i] || gr[i]%2==1) return false;
return true;
}
void euler(int x)
{
int y;
while (!a[x].empty())
{
y=a[x].front();
a[x].pop_front();
for (list<int>::iterator j =a[y].begin();j!=a[y].end();j++)
if (*j==x)
{
a[y].erase(j);
break;
}
S.push(x);
x=y;
}
}
void solve()
{
int x=1;
do
{
euler(x);
x=S.top(); S.pop();
sol.push_back(x);
}
while (S.size());
for (int i=0;i<sol.size();i++) fprintf(g,"%d ",sol[i]);
}
int main()
{
read();
if (!pre()) { fprintf(g,"-1"); return 0;}
solve();
return 0;
}