Pagini recente » Cod sursa (job #328675) | Cod sursa (job #2260895) | Cod sursa (job #2688938) | Cod sursa (job #138104) | Cod sursa (job #357370)
Cod sursa(job #357370)
#include<fstream>
using namespace std;
struct lista{int nod;lista *next;} *v[100005];
int deg[100005],cic[100004],nrcic=0,nr=0,n,m;;
char viz[100005];
void adauga(lista* &l,int x)
{lista *q=new lista;
q->nod=x;
q->next=l;
l=q;
}
void pop(lista* &l,int &x)
{ lista *q=l;
x=q->nod;
l=l->next;
delete q;
}
void sterge(int x,int y)
{lista *q=v[x];
lista *pg=NULL;
while(q)
{if(q->nod==y)
{if(pg) pg->next=q->next;
else v[x]=q->next;
delete q; return; }
pg=q;q=q->next;
}
}
int dfs(int x)
{nr++;
viz[x]=1;
for(lista *p=v[x];p!=NULL;p=p->next)
if(!viz[p->nod])
{viz[p->nod]=1;
dfs(p->nod);}
}
int eulerian()
{dfs(1);
if(n!=nr) return 0;
for(int i=1;i<=n;i++) if(deg[i]%2==1) return 0;
return 1;
}
int euler(int nd)
{int x;
while(v[nd])
{pop(v[nd],x);
sterge(x,nd);
euler(x);
}
cic[++nrcic]=nd;
}
int main()
{freopen("ciclueulerian.in","r",stdin);
freopen("ciclueulerian.out","w",stdout);
scanf("%d %d",&n,&m);
int a,b;
for(int i=1;i<=n;i++) {deg[i]=viz[i]=0;v[i]=NULL;}
for(int i=1;i<=m;i++)
{scanf("%d %d",&a,&b); adauga(v[a],b);adauga(v[b],a);deg[a]++;deg[b]++;}
int v=eulerian();
if(v!=1) printf("%d",-1);
else {euler(1);for(int i=1;i<nrcic;i++) printf("%d ",cic[i]);}
return 0;
}