Cod sursa(job #2280555)

Utilizator LorenaMariaHantig Lorena LorenaMaria Data 10 noiembrie 2018 20:26:05
Problema Ciclu Eulerian Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector < pair <int,int> > v[500005];
int n,m,x,k,a[500005],i,y;
void ciclu_eulerian(int x)
{ while(!v[x].empty())
  { int p=v[x].back().second,q=v[x].back().first;
    v[x].pop_back();
    if(!a[p])
    { a[p]=1;
      ciclu_eulerian(q);
    }
  }
  a[k++]=x;
}
int main()
{ in>>n>>m;
  for(int i=1;i<=m;i++)
  { in>>x>>y;
    v[x].push_back({y,i});
    v[y].push_back({x,i});
  }
  for(int i=1;i<=n;i++)
    if(v[i].size()%2!=0)
    { out<<"-1";
      in.close();
      out.close();
      return 0;
    }
  ciclu_eulerian(1);
  if(k==1)
  { out<<"-1";
    in.close();
    out.close();
    return 0;
  }
  for(int i=1;i<k;i++)
    out<<a[i]<<" ";
  in.close();
  out.close();
  return 0;
}