Cod sursa(job #1714967)

Utilizator DjokValeriu Motroi Djok Data 9 iunie 2016 20:05:41
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<bits/stdc++.h>
using namespace std;

typedef struct lnod {
    int info;
    lnod *next;
}*nod;

int i,n,m,x,y,grad[100005],st[500005],nr,rs[500005];
nod lda[100005];

void add(int x,nod &y) {
    nod p=new lnod;
    p->info=x;
    p->next=y;
    y=p;
}

int main()
{
  ifstream cin("ciclueuler.in");
  ofstream cout("ciclueuler.out");

  ios_base::sync_with_stdio(0); cin.tie(0);

  for(cin>>n>>m;m;--m)
  {
    cin>>x>>y;
    add(x,lda[y]); ++grad[y];
    add(y,lda[x]); ++grad[x];
  }

  for(i=1;i<=n;++i) if(grad[i]&1) return cout<<"-1\n",0;

  for(st[++nr]=1;nr;)
  if(!lda[st[nr]]) rs[++rs[0]]=st[nr--];
  else {
         x=st[nr]; y=lda[x]->info;
         lda[x]=lda[x]->next;
         st[++nr]=y;

         if(lda[y]->info==x) lda[y]=lda[y]->next;
         else for(nod p=lda[y];p->next;p=p->next)
              if(p->next->info==x) 
              {
                p->next=p->next->next;
                break;
              }
       }

  for(i=1,--rs[0];i<=rs[0];++i) cout<<rs[i]<<" \n"[i==rs[0]];

 return 0;
}