Pagini recente » Cod sursa (job #2445277) | Cod sursa (job #1475974) | Cod sursa (job #2816998) | Cod sursa (job #375895) | Cod sursa (job #1018189)
#include<fstream>
#include<vector>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int Nmax = 100005;
struct stack{
int Stack[Nmax],K;
void push(int x){Stack[++K]=x;}
void pop(){K--;}
int empty(){return K==0;}
int top(){return Stack[K];}
} St;
vector<int> G[Nmax],S;
int N,M;
int mark[Nmax],grad[Nmax];
void DFS(int i){
mark[i]=1;
for(vector<int>::iterator it=G[i].begin();it!=G[i].end();++it) if(!mark[*it]) DFS(*it);
}
int Eulerian(){
DFS(1);
for(int i=1;i<=N;i++) if(!mark[i] || grad[i]%2==1) return 0;
return 1;
}
void remove_edge(int a,int b){
G[a].erase(G[a].begin());
for(vector<int>::iterator it=G[b].begin();it!=G[b].end();++it) if(*it==a){
G[b].erase(it);
return;
}
}
void Euler(int i){
while(G[i].size()){
int son=G[i].front();
remove_edge(i,son);
St.push(i);
i=son;
}
}
int main(){
in>>N>>M;
for(int i=1;i<=M;i++){
int a,b;
in>>a>>b;
G[a].push_back(b); grad[a]++;
G[b].push_back(a); grad[b]++;
}
if(!Eulerian()){
out<<-1;
return 0;
}
int v=1;
do{
Euler(v);
v=St.top(); St.pop();
S.push_back(v);
} while(!St.empty());
for(vector<int>::iterator it=S.begin();it!=S.end();++it) out<<*it<<' ';
return 0;
}