Pagini recente » Cod sursa (job #652525) | Cod sursa (job #889456) | Cod sursa (job #2425116) | Cod sursa (job #1939874) | Cod sursa (job #2084370)
/// O(n^2)
#include <fstream>
#include <vector>
#include <list>
#define Nmax 100001
using namespace std;
ifstream f("ciclueuler.in"); ofstream g("ciclueuler.out");
vector <int> G[Nmax];
list <int> Q;
int N,M,viz[Nmax],gr[Nmax];
void euler(int x)
{ Q.push_back(x);
while(!Q.empty())
{ x=Q.front();
if(G[x].empty()) {Q.pop_front(); g<<x<<' ';}
else
{ int i=G[x].back(); G[x].pop_back();
Q.push_front(i);
vector<int>::iterator it=G[i].begin(),sf=G[i].end();
for(;it!=sf;++it)
if(*it==x) {G[i].erase(it); break;}
}
}
}
void dfs(int nod)
{ viz[nod]=true;
for(unsigned int i=0;i<G[nod].size();++i)
if(!viz[G[nod][i]]) dfs(G[nod][i]);
}
int main()
{ f>>N>>M;
for(int x,y,i=1;i<=M;i++)
{ f>>x>>y; gr[x]++; gr[y]++;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
for(int i=1;i<=N;++i)
if(!viz[i]) {g<<-1; return 0;}
for(int i=1;i<=N;++i)
if(gr[i]%2) {g<<-1; return 0;}
euler(1);
return 0;
}