Pagini recente » Cod sursa (job #2326387) | Cod sursa (job #2259637) | Cod sursa (job #2822679) | Cod sursa (job #3151931) | Cod sursa (job #973132)
Cod sursa(job #973132)
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector<list<int> >g;
int m, n, x, y;
queue<int>q;
stack<int>s;
bool vis[100001];
inline bool CheckEuler()
{
q.push(1);
while(!q.empty())
{
int x=q.front(); q.pop();
for(list<int>::iterator it=g[x].begin(); it!=g[x].end(); it++ )
if(!vis[*it])
{
vis[*it]=1;
q.push(*it);
}
}
for(int i = 1; i<= n; i++ )
if(g[i].size()&1 || (!vis[i]&&g[i].size()) )
return 0;
return 1;
}
void Euler(int x)
{
s.push(x);
while (s.size())
{
x = s.top();
if (!g[x].size())
{
fout<<x<<" ";
s.pop();
continue;
}
int y = *g[x].begin();
g[x].erase(g[x].begin());
list<int>::iterator it=g[y].begin();
for(; *it!=x; it++ );
g[y].erase(it);
s.push(y);
}
}
int main()
{
fin>>n>>m;
g.resize(n+1);
for(;m--;)
{
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
if(!CheckEuler())
fout<<-1;
else Euler(1);
fin.close();
fout.close();
return 0;
}