Pagini recente » Cod sursa (job #3248338) | Cod sursa (job #1955311) | Cod sursa (job #1955171) | Cod sursa (job #2767420) | Cod sursa (job #777262)
Cod sursa(job #777262)
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
#define pb push_back
using namespace std;
vector<int> a[100002],L;
vector<int>::iterator it;
int deg[100002],N,M;
bool viz[100002];
queue<int> Q;
stack<int> s;
void bfs(){
int v;
Q.push(1); viz[1]=1;
while(!Q.empty()){
v=Q.front(); Q.pop();
for(it=a[v].begin();it!=a[v].end();++it)
if(!viz[*it])
Q.push(*it),viz[*it]=1;
}
}
bool conex(){
bfs();
for(int i=2;i<=N;++i)
if(!viz[i])return 0;
return 1;
}
void sterge(int v,int w){
deg[v]--; deg[w]--;
a[v].erase(a[v].begin());
for(it=a[w].begin();it!=a[w].end();++it)
if(*it==v)
{
a[w].erase(it);
break;
}
}
void euler(int v){
while(1)
{
if(a[v].empty())break;
int w=*a[v].begin();
s.push(v);
sterge(v,w);
v=w;
}
}
int main(void){
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int i,x,y,v;
fin>>N>>M;
for(i=1;i<=M;++i)
{
fin>>x>>y;
a[x].pb(y); deg[x]++;
a[y].pb(x); deg[y]++;
}
if(conex==0){ fout<<"-1\n"; return 0; }
for(i=1;i<=N;++i)if(deg[i]&1){ fout<<"-1\n"; return 0; }
v=1;
do{
euler(v);
v=s.top(); s.pop();
L.pb(v);
}while(!s.empty());
for(it=L.end()-1;it!=L.begin()-1;--it)fout<<*it<<' ';
return 0;
}