Cod sursa(job #261579)

Utilizator MciprianMMciprianM MciprianM Data 18 februarie 2009 15:06:16
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#pragma comment(linker, "/STACK:16777216")
#include<fstream>
#include<vector>
#define MAXN 100009
using namespace std;
vector<int> G[MAXN];
int d[MAXN], n, m;
int apel;
int stiva[5*MAXN],vf;
void df(int nod){
  int l=G[nod].size(), i, l2, j;
  for(i=0;i<l;i++)
    if(G[nod][i]!=(-1)){
      apel=G[nod][i];
      G[nod][i]=-1;
      l2=G[apel].size();
      for(j=0;j<l2;j++)
        if(G[apel][j]==nod)
          {G[apel][j]=-1;break;}
      df(apel);
    }
    stiva[vf++]=nod;
}
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;
  }
  df(1);
  ofstream g("ciclueuler.out");
  vf--;
  for(i=0;i<vf;i++)
    g<<stiva[i]<<' ';
  g<<"\n";
  g.close();
  return 0;
}