Cod sursa(job #1235785)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 30 septembrie 2014 17:52:05
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <cstdio>
#define max_n 100020
#include <queue>
#include <vector>
#include <list>

using namespace std;

struct stk{
  int node;
  stk *link;
} *st;
int n,m;
list <int> q[max_n];
vector <int> ls;
queue <int> kj;
int grd[max_n];
int s[max_n];


inline void add_stn(stk *&f,int x){
  if(f==NULL){
    f=new stk;
    f->node=x;
    f->link=NULL;
    return;
  }
   stk *c=new stk;
   c->node=x;
   c->link=f;
   f=c;

}

inline void del_stn(stk *&f){
  stk *c=f;
  f=f->link;
  delete c;
}

void read(){
  freopen("ciclueuler.in","r",stdin);
  scanf("%d %d",&n,&m);
  int x,y;
  while(m--){
    scanf("%d%d",&x,&y);
    grd[x]++;
    q[x].push_back(y);
    grd[y]++;
    q[y].push_back(x);
  }
}

void solve(){
  int i,r,t;

  kj.push(1);
  while(!kj.empty()){
    i=kj.front();
    kj.pop();
    s[i]=1;
    for(list <int> :: iterator it=q[i].begin();it!=q[i].end();++it)
        if(!s[*it])
           kj.push(*it);
  }
  for(i=1;i<=n;i++)
     if((grd[i]%2)||(!s[i])){
          printf("-1\n");
          return;
       }
       r=1;
   do{
      while(!q[r].empty()){
          t=q[r].front();
          add_stn(st,r);
          q[r].pop_front();
          grd[r]--;
          grd[t]--;
          for(list <int> ::iterator it=q[t].begin();it!=q[t].end();++it)
          if(*it == r){
                q[t].erase(it);
                    break;
            }
          r=t;
      }

     r=st->node;
     del_stn(st);
    ls.push_back(r);
  }while(st!=NULL);

  for(vector <int> :: iterator tr=ls.begin();tr!=ls.end();++tr)
        printf("%d ",*tr);
  printf("\n");
}

int main()
{
  read();
  freopen("ciclueuler.out","w",stdout);
  solve();

    return 0;
}