Cod sursa(job #2361677)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 2 martie 2019 17:52:34
Problema Ciclu Eulerian Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define maxn 100000
#define maxm 500000
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

vector <int> g[maxn+5];
map<pii,int> hh;

ifstream fin ( "ciclueuler.in" );
ofstream fout ( "ciclueuler.out" );

void euler ( int nod )
{
  int i, nn;
  for ( i = 0; i < g[nod].size(); i++ )
  {
    nn = g[nod][i];
    if ( hh[{nod,nn}] > 0 )
    {
      hh[{nod,nn}]--; hh[{nn,nod}]--;
      euler (nn);
    }
  }
  fout << 1 + nod << ' ';
}

int main ()
{
  int n, m; fin >> n >> m;

  int i, j, a, b;
  for ( i = 0; i < m; i++ )
  {
    fin >> a >> b; a--; b--;
    g[a].push_back (b); hh[{a,b}]++;
    g[b].push_back (a); hh[{b,a}]++;
  }

  i = 0; while ( i < n && g[i].size() % 2 == 0 ) i++;
  if ( i < n ) fout << -1;
  else
  {
    i = 0; while ( i < n && g[i].size() == 0 ) i++;
    euler (i);
  }

  fin.close();
  fout.close();

  return 0;
}