Pagini recente » Cod sursa (job #2247383) | Istoria paginii utilizator/cristiana_valeca | Profil RolandPetrean | Cod sursa (job #193445) | Cod sursa (job #794996)
Cod sursa(job #794996)
#include <stdio.h>
#include <queue>
#include <stack>
#include <list>
using namespace std;
list<int> G[100005];
int n,m;
int deg[100005];
queue<int> q;
int viz[100005];
stack<int> S;
list<int> L;
bool eulerianAndConex(){
int u;
for(int i=1;i<=n;i++) if(deg[i]%2!=0) return false;
q.push(1);viz[1]=1;
while(!q.empty()){
u=q.front();q.pop();
for(list<int>::iterator it = G[u].begin();it!=G[u].end();it++)
if(!viz[*it]){viz[*it]=1;q.push(*it);}
}
for(int i=1;i<=n;i++) if(!viz[i]) return false;
return true;
}
void eraseEdge(int u,int v){
deg[u]--;deg[v]--;
for(list<int>::iterator it = G[u].begin();it!=G[u].end();it++)
if((*it)==v){ G[u].erase(it);break;}
for(list<int>::iterator it = G[v].begin();it!=G[v].end();it++)
if((*it)==u){ G[v].erase(it);break;}
}
void euler(int n){
//S.push(n);
int u=n,v;
do
{
while(true){
if(G[u].empty()) break;
v=G[u].front();
eraseEdge(u,v);
S.push(u);
u=v;
}
u=S.top();S.pop();
L.push_back(u);
}while(!S.empty());
}
void euler2(int u){
int v;
while(!G[u].empty()){
v=G[u].front();eraseEdge(u,v);
euler2(v);
L.push_back(u);
}
}
int main(){
int x,y;
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d",&x);scanf("%d",&y);
G[x].push_back(y);G[y].push_back(x);
deg[x]++;deg[y]++;
}
if(!eulerianAndConex()){printf("-1");return 0;}
euler2(1);
for(list<int>::iterator it = L.begin();it!=L.end();it++){
printf("%d ",(*it));
}
return 0;
}