Cod sursa(job #2112323)

Utilizator tanasaradutanasaradu tanasaradu Data 23 ianuarie 2018 12:38:40
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
const int Nmax = 100005;
const int Mmax = 500015;
vector < int > L[Mmax];
int n , X[Mmax] , Y[Mmax] , m , k , sol[Mmax];
unsigned int ind[Mmax];
bool viz[Mmax];
inline void Read()
{
    fin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> X[i] >> Y[i];
        L[X[i]] . push_back(i);
        L[Y[i]] . push_back(i);
    }
}
inline bool Check()
{
    for(int i = 1 ; i <= n ; i++)
    {
        int k = L[i] . size();
        if(k & 1)
            return false;
    }
    return true;
}
inline void DFS(int nod)
{
    while(ind[nod] < L[nod] . size())
    {
        int i = L[nod][ind[nod]++];
        if(!viz[i])
        {
            viz[i] = true;
            DFS(X[i] + Y[i] - nod);
        }
    }
    ++k;
    sol[k] = nod;
}
int main()
{
   Read();
   if(! Check())
    fout << "-1\n";
   else
   {
       DFS(X[1]);
       for(int i = 1 ; i < k ; i++)
        fout << sol[i] << " ";
       fout << "\n";
   }
   fin.close();
   fout.close();
    return 0;
}