Pagini recente » Istoria paginii utilizator/justmarktmd | Cod sursa (job #2534853) | Cod sursa (job #2060949) | Cod sursa (job #2926840) | Cod sursa (job #694566)
Cod sursa(job #694566)
#include<cstdio>
#include<list>
#include<stack>
#include<bitset>
using namespace std;
#define Nmax 100001
list<int> G[Nmax], sol;
stack<int> S;
bitset<Nmax> use;
int N, M, grad[Nmax], ok(1);
void DF(int nod) {
use[nod]=1;
for(list<int>:: iterator it=G[nod].begin(); it!=G[nod].end(); ++it)
if(!use[*it])
DF(*it);
}
void sterge(int nod, int nod_vecin) {
grad[nod]--;
grad[nod_vecin]--;
G[nod].pop_front();
for(list<int>:: iterator it=G[nod_vecin].begin(); it!=G[nod_vecin].end(); ++it)
if(*it==nod) {
G[nod_vecin].erase(it);
break;
}
}
void euler(int nod) {
while(1) {
if(G[nod].empty()==true)
break;
S.push(nod);
int nod_vecin=G[nod].front();
sterge(nod,nod_vecin);
nod=nod_vecin;
}
}
int main() {
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
int i, j, nod;
scanf("%d %d",&N,&M);
while(M--) {
scanf("%d %d",&i,&j);
G[i].push_back(j);
G[j].push_back(i);
grad[i]++;
grad[j]++;
}
for(i=1; i<=N; i++)
if(grad[i]%2==1) {
ok=0;
break;
}
if(ok) {
DF(1);
for(i=1; i<=N; i++)
if(!use[i]) {
ok=0;
break;
}
}
if(!ok) {
printf("-1\n");
return 0;
}
nod=1;
do {
euler(nod);
nod=S.top();
S.pop();
sol.push_back(nod);
} while(!S.empty());
for(list<int>:: iterator it=sol.begin(); it!=sol.end(); ++it)
printf("%d ",*it);
return 0;
}