Cod sursa(job #774072)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 3 august 2012 13:43:40
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<fstream>
#include<string>
using namespace std;
typedef struct celula{
         int nod,pos;
         struct celula *next;
         }*lista;
lista g[100001],v;
bool much[500001],ok;
string s;
int b[500001];
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

void dfs(){
     int st=1;
      b[st]=1;
     while (st>0) {
      bool ok=true;
      for(lista p=g[b[st]];p;p=p->next)
       if (much[p->pos]==false){much[p->pos]=true; ++st; b[st]=p->nod; ok=false; break; }
      if (ok==true) { if (st>1) fout<<b[st]<<" "; --st; }
      }
   }
      
int main(void){
    int i,n,m,x,y,j;
    fin>>n>>m; getline(fin,s);
    for(i=1;i<=m;++i){
       /*getline(fin,s); x=y=0;
        for(j=0;j<s.length();++j)             
          if(s[j]==' ')break;
            else x=(x*10)+(s[j]-'0');
        ++j;
        while(j<s.length()){ y=(y*10)+(s[j]-'0'); ++j; }*/
        fin>>x>>y;
        ++b[x]; ++b[y];
        v=new celula; v->nod=y; v->pos=i; v->next=g[x]; g[x]=v;                     
        v=new celula; v->nod=x; v->pos=i; v->next=g[y]; g[y]=v;
       }
    for (i=1; i<=n; ++i) if (b[i]%2==1) ok=true;
    if (ok==true) fout<<"-1"; else dfs();
   return(0);
}