Cod sursa(job #2361733)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 2 martie 2019 18:12:07
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 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 <pii> g[maxn+5];
int viz[maxm+5], nv[maxn+5];

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

void euler ( int nod )
{
  int i;
  for ( ; nv[nod] < g[nod].size(); )
  {
    if ( viz[g[nod][nv[nod]].se] == 0 )
    {
      viz[g[nod][nv[nod]].se] = 1;
      nv[nod]++;
      euler ( g[nod][nv[nod]-1].fi );
    }
    else nv[nod]++;
  }
  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,i});
    g[b].push_back ({a,i});
  }

  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;
}