Pagini recente » Cod sursa (job #2121518) | Cod sursa (job #1842818) | Cod sursa (job #471035) | Cod sursa (job #1991001) | Cod sursa (job #782267)
Cod sursa(job #782267)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<bitset>
using namespace std;
vector <int> v[100001],a;
int gr[100001],n,m,c[100001],start,l;
bitset <100001> viz;
stack <int> s;
inline void bfs(int nod)
{
int st,dr;
st=1;
dr=1;
viz[nod]=1;
c[1]=nod;
while(st<=dr) {
for(vector <int> :: iterator it=v[c[st]].begin();it!=v[c[st]].end();it++)
if(viz[*it]==0) {
viz[*it]=1;
c[++dr]=*it;
}
st++;
}
}
inline int conex()
{
int i;
for(i=1;i<=n;i++)
if(gr[i]%2==1)
return 0;
bfs(1);
for(i=1;i<=n;i++)
if(viz[i]==0)
return 0;
return 1;
}
inline void sterge(int x, int y)
{
for(vector <int> :: iterator it=v[x].begin();it!=v[x].end();it++)
if(*it==y) {
v[x].erase(it);
return;
}
}
inline void euler(int nod)
{
int x;
while(v[nod].empty()==0) {
x=v[nod].back();
s.push(nod);
v[nod].pop_back();
sterge(x,nod);
nod=x;
}
}
int main ()
{
int i,x,y;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
f>>n>>m;
for(i=1;i<=m;i++) {
f>>x>>y;
gr[x]++;
gr[y]++;
v[x].push_back(y);
v[y].push_back(x);
}
f.close();
if(conex()) {
start=1;
do {
euler(start);
start=s.top();
s.pop();
a.push_back(start);
}while(s.empty()==0);
for(vector <int> :: iterator it=a.begin();it!=a.end();it++)
g<<*it<<" ";
}
else g<<"-1";
g.close();
return 0;
}