Cod sursa(job #2201364)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 4 mai 2018 15:44:19
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100010
#define MMAX 500010

using namespace std;

int n,m,x,y,sz;
int ans[MMAX];
bool ms[MMAX];
vector<pair<int,int>> nd[NMAX];
void euler(int nod){
  while(nd[nod].size()){
    if(!ms[nd[nod][0].second]){
      ms[nd[nod][0].second]=true;
      euler(nd[nod][0].first);
    }
    if(nd[nod].size()){
      swap(nd[nod][0],nd[nod][nd[nod].size()-1]);
      nd[nod].erase(nd[nod].begin()+nd[nod].size()-1);
    }
  }
  ans[++sz]=nod;
}

int main()
{
    ifstream f ("ciclueuler.in");
    ofstream g ("ciclueuler.out");
    f>>n>>m;
    for(int i=1;i<=m;i++)
      f>>x>>y,
      nd[x].push_back(make_pair(y,i)),
      nd[y].push_back(make_pair(x,i));
    for(int i=1;i<=n;i++)
      if(nd[i].size()%2){
        g<<"-1\n";
        return 0;
      }
    for(int i=1;i<=n;i++)
      if(nd[i].size()){
        euler(i);
        break;
      }
    for(int i=1;i<sz;i++) g<<ans[i]<<" ";
    f.close ();
    g.close ();
    return 0;
}