Cod sursa(job #2056023)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 4 noiembrie 2017 00:18:51
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <list>
using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define NMAX 100003
int x,y,N,M,d[NMAX];

vector<int> v[NMAX];
 stack<int> s;
  list<int> l;

void Ciclu_Eulerian(int xp)
{
    s.push(xp);
    while( !s.empty() )
    {
       int n = s.top();
       vector<int>::iterator it = v[n].begin();
       if( it != v[n].end() )
       {
           s.push(*it);
           v[*it].erase( find(v[*it].begin(),v[*it].end(),n) );
           v[n].erase(it);
       }
       else
       {
           l.push_back(n);
           s.pop();
       }
    }
}

int main()
{
    fin>>N>>M;
    for(int i = 1 ; i <= M ; i++)
    {
        fin>>x>>y;
        d[x]++; d[y]++;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1 ; i <= N ; i++)
        if( d[i]%2 != 0 )
    {
        fout<<-1;
        return 0;
    }
    Ciclu_Eulerian(1);
    l.pop_front();
    while( !l.empty() )
    {
        fout << l.back() << ' ';
        l.pop_back();
    }
    return 0;
}