Cod sursa(job #2056028)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 4 noiembrie 2017 00:38:14
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 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;

void Ciclu_Eulerian(int xp)
{
    bool ok = 1;
    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);
           M--;
           v[*it].erase( find(v[*it].begin(),v[*it].end(),n) );
           v[n].erase(it);
       }
       else
       {
           if( n == xp )
           {
               if( ok == 1 ){
               fout<<n<<' ';
               ok = 0; }
           }
           else
               fout<<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);
    fin.close();
    fout.close();
    return 0;
}