Pagini recente » Cod sursa (job #140463) | Cod sursa (job #108903) | Cod sursa (job #1316695) | Cod sursa (job #2690810) | Cod sursa (job #239782)
Cod sursa(job #239782)
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
const int NMAX=100001;
int N,M,deg[NMAX];
vector<int> Adj[NMAX],sol;
queue<int> Q;
bitset<NMAX> u;
void bf(int vf){
int x;
vector<int>::iterator it;
Q.push(vf);
u[vf]=1;
while (!Q.empty()){
x=Q.front();Q.pop();
for (it=Adj[x].begin();it!=Adj[x].end();++it)
if (!u[*it]) u[*it]=1,Q.push(*it);
}
}
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
void sterge(int x,int vf){
Adj[vf].pop_back();
vector<int>::iterator it;
for (it=Adj[x].begin();it!=Adj[x].end();++it)
if (*it==vf){
Adj[x].erase(it);
break;}
}
stack<int> S;
void euler(){
int vf,x;
S.push(1);
while (!S.empty()){
vf=S.top();
if (Adj[vf].empty()){
sol.push_back(vf);
S.pop();
continue;}
x=Adj[vf].back();
sterge(x,vf);
S.push(x);}
}
int main(){
int i,j;
fin>>N>>M;
while (M--){
fin>>i>>j;
Adj[i].push_back(j);
Adj[j].push_back(i);
++deg[i];++deg[j];}
bool ok=true;
bf(1);
for (i=1;i<=N && ok;++i)
if (!u[i] || deg[i]&1)
ok=false;
if (!ok){
fout<<"-1\n";
return 0;}
euler();
sol.pop_back();
vector<int>::iterator it;
for (it=sol.begin();it!=sol.end();++it)
fout<<*it<<' ';
return 0;
}