Cod sursa(job #1503032)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 15 octombrie 2015 14:24:47
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

typedef struct celula {
        int nod;
        celula *next;
        }*lista;
lista graf[100005],v;
int n,m,i,x,y,sol[500005],st[500005],dg[100005],vf,nrs;

int main(void) {
     ifstream cin("ciclueuler.in");
     ofstream cout("ciclueuler.out");
     
     cin>>n>>m;
     
     for (i=1; i<=m; ++i) {
         cin>>x>>y;
         v=new celula; v->nod=x; v->next=graf[y]; graf[y]=v;
         v=new celula; v->nod=y; v->next=graf[x]; graf[x]=v;
         ++dg[x];
         ++dg[y];
         }
         
    bool ok=1;
    for (i=1; i<=n; ++i) 
     if ( dg[i]%2==1 ) { ok=0; break; }
     
    if (!ok) {
             cout<<"-1";
             return 0;
             }
             
    vf=1;
    st[1]=1;
    
    while (vf>0) {
          
          int nodc=st[vf];
          
          if (graf[nodc]==NULL) {
                             sol[++nrs]=nodc;
                             --vf;
                             continue;
                             }
                             
          int vecin=graf[nodc]->nod;
          graf[nodc]=graf[nodc]->next;
          st[++vf]=vecin;
          
          if (graf[vecin]->nod==nodc) graf[vecin]=graf[vecin]->next;
          else
           for (lista p=graf[vecin]; p->next!=NULL; p=p->next)
            if (p->next->nod==nodc) {
                                    p->next=p->next->next;
                                    break;
                                    }
          }
 
    for (i=1; i<nrs; ++i) cout<<sol[i]<<" ";   
    
    return 0;
}