Pagini recente » Cod sursa (job #2946825) | Cod sursa (job #39054) | Cod sursa (job #2727961) | Cod sursa (job #532246) | Cod sursa (job #1496439)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100070
stack <int> S;
vector <int> v[MAX];
int gr[MAX];
vector <int> sol;
bitset <MAX> viz;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
queue <int> Q;
inline void bfs(int nod)
{
viz[nod]=1;
Q.push(nod);
while(!Q.empty())
{
nod=Q.front();
Q.pop();
for(vector <int> ::iterator it=v[nod].begin(); it!=v[nod].end(); ++it)
{
if(viz[*it]==0)
{ Q.push(*it);
viz[*it]=1;
}
}
}
}
inline void euler()
{
S.push(1);
while(!S.empty())
{
int nod=S.top();
if(!v[nod].empty())
{
int nou=v[nod].back();
S.push(nou);
v[nod].pop_back();
v[nou].erase(find (v[nou].begin(),v[nou].end(),nod));
}
else
{
sol.push_back(nod);
S.pop();
}
}
}
int main()
{
int n,m,x,y,i,j;
in>>n>>m;
for(i=1; i<=m; i++)
{
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
gr[x]++;
gr[y]++;
}
bfs(1);
euler();
for(i=1; i<=n; i++)
if(gr[i]%2||viz[i]==0)
{
out<<-1;
return 0;
}
for(i=0; i<sol.size()-1; i++)
out<<sol[i]<<" ";
return 0;
}