Pagini recente » Cod sursa (job #1381093) | Istoria paginii utilizator/claudia.georgiana | Cod sursa (job #2094958) | Cod sursa (job #352354) | Cod sursa (job #640261)
Cod sursa(job #640261)
#include<cstdio>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
int N,M,cnt,poz;
typedef pair <int,int> hh;
vector <hh> nr[100010];
char viz[100100],fol[100100];
queue <int> Q;
stack <int> S;
unsigned int s[100100];
void df(){
int x;
viz[1]=true;
S.push(1);
while(!S.empty()){
x=S.top();
while(s[x]<nr[x].size()){
if(viz[nr[x][s[x]].first])
++s[x];
else
break;
}
if(s[x]==nr[x].size()){
--cnt;
S.pop();
continue;
}
S.push(nr[x][s[x]].first);
viz[nr[x][s[x]].first]=true;
++s[x];
}
}
void euler(){
int x;
S.push(1);
while(!S.empty()){
x=S.top();
while(s[x]<nr[x].size()){
if(fol[ nr[x][s[x]].second ])
++s[x];
else
break;
}
if(s[x]==nr[x].size()){
Q.push(x);
S.pop();
continue;
}
fol[ nr[x][s[x]].second ]=1;
S.push(nr[x][s[x]].first);
++s[x];
}
}
int main(){
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int i,x,y;
f>>N>>M;
for(i=1;i<=M;++i){
f>>x>>y;
nr[x].push_back( hh(y,i) );
nr[y].push_back( hh(x,i) );
}
for(i=1;i<=N;++i){
if(nr[i].size()%2){
g<<"-1\n";
f.close();
g.close();
return 0;
}
}
cnt=N;
df();
if(cnt){
g<<"-1\n";
f.close();
g.close();
return 0;
}
for(i=0;i<=N;++i)
s[i]=0;
euler();
Q.pop();
for(;!Q.empty();Q.pop())
g<<Q.front()<<' ';
g<<'\n';
f.close();
g.close();
return 0;
}