Pagini recente » Cod sursa (job #934006) | Cod sursa (job #1574850) | Cod sursa (job #2804831) | Cod sursa (job #222634) | Cod sursa (job #766043)
Cod sursa(job #766043)
#include<iostream>
#include<fstream>
#include<stack>
#include<list>
#include<bitset>
using namespace std;
list <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(list <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(list <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].front();
s.push(nod);
v[nod].pop_front();
sterge(x,nod);
nod=x;
}
}
#define DIM 10000
char buff[DIM];
int poz=0;
void citeste(int &numar)
{
numar = 0;
while(buff[poz]<'0'||buff[poz]>'9')
if (++poz==DIM) {
fread(buff,1,DIM,stdin);
poz=0;
}
while('0'<=buff[poz]&&buff[poz]<='9') {
numar=numar*10+buff[poz]-'0';
if (++poz==DIM) {
fread(buff,1,DIM,stdin);
poz=0;
}
}
}
int main ()
{
int i,x,y;
freopen("ciclueuler.in","r",stdin);
ofstream g("ciclueuler.out");
citeste(n);
citeste(m);
for(i=1;i<=m;i++) {
citeste(x);
citeste(y);
gr[x]++;
gr[y]++;
v[x].push_back(y);
v[y].push_back(x);
}
fclose(stdin);
if(conex()) {
start=1;
do {
euler(start);
start=s.top();
s.pop();
a.push_back(start);
}while(s.empty()==0);
for(list <int> :: iterator it=a.begin();it!=a.end();it++)
g<<*it<<" ";
}
else g<<"-1";
g.close();
return 0;
}