Cod sursa(job #262791)

Utilizator MciprianMMciprianM MciprianM Data 19 februarie 2009 17:29:39
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<stack>
#include<list>
#define MAXN 100009
using namespace std;
list<int> G[MAXN];
typedef list<int>::iterator IT;
int n, m;
int d[MAXN];
stack<int> stiva,rsp;
int main(){
  int i, x, y, ok=1;
  ifstream f("ciclueuler.in");
  f>>n>>m;
  for(i=0;i<m;i++){
    f>>x>>y;
    G[x].push_back(y);
    G[y].push_back(x);
    d[x]++;d[y]++;
  }
  f.close();
  for(i=1;i<=n;i++)
    if(d[i]&1){
      ok=0;
      break;
  }
  if(!ok){
    ofstream g("ciclueuler.out");
    g<<"-1\n";
    g.close();
    return 0;
  }
  stiva.push(1);
  IT it,end;
  int svf;
  while(!(stiva.empty())){
    svf=stiva.top();
    if(G[svf].empty()){
      rsp.push(svf);
      stiva.pop();
    }
    else {
      stiva.push(*G[svf].begin());
      G[svf].pop_front();
      x=svf;
      ok=stiva.top();
      end=G[ok].end();
      for(it=G[ok].begin();it!=end;++it)
        if(*it==x){
          G[ok].erase(it);
          break;
        }
    }
  }
  ofstream g("ciclueuler.out");
  while(rsp.size()>1){
    g<<rsp.top()<<' ';
    rsp.pop();
  }
  g<<'\n';
  g.close();
  return 0;
}