Cod sursa(job #2928421)

Utilizator vlad_dimuVlad Dimulescu vlad_dimu Data 22 octombrie 2022 21:33:52
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAXN 100000
using namespace std;

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

vector <int> graph[MAXN];

stack <int> cycle;
stack <int> finalCycle;

int main(){
  int n, m, i, x, y, gradPar, nod, vecin;
  fin >> n >> m;
  for( i = 0; i < m; i++ ){
    fin >> x >> y;
    graph[x - 1].push_back(y - 1);
    graph[y - 1].push_back(x - 1);
  }

  gradPar = 1;
  for( i = 0; i < n; i++ )
    if( graph[i].size() % 2 == 1 )
      gradPar = -1;

  if( gradPar == -1 )
    fout << -1;
  else{
    cycle.push(0);

    while( cycle.size() ){
      nod = cycle.top();

      if( graph[nod].size() ){
        vecin = graph[nod].back();

        //stergem muchia
        graph[nod].pop_back();
        graph[vecin].erase( find( graph[vecin].begin(), graph[vecin].end(), nod ) );
        m--;

        cycle.push(vecin);
      }
      else{
        finalCycle.push(nod);
        cycle.pop();
      }
    }

    if( m != 0 )
      fout << -1;
    else{
      while (finalCycle.size()) {
        fout << finalCycle.top() + 1 << ' ';
        finalCycle.pop();
      }
    }
  }
  return 0;
}