Cod sursa(job #2146261)

Utilizator tanasaradutanasaradu tanasaradu Data 27 februarie 2018 21:36:20
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
const int Nmax = 100005;
int X[Nmax] , Y[Nmax] , ind[Nmax] , n , m , sol[Nmax] , k;
vector < int > L[Nmax];
bool viz[Nmax];

/// conditia necesara si suficienta ca un graf sa admita ciclu eulerian e ca fiecare
/// nod din graf sa aiba numarul de adiacenti par


inline bool CHECK()
{
    for(int i = 1 ; i <= n ; i++)
    {
        int dim = L[i] . size();
        if(dim & 1)
            return false;
    }
    return true;
}
inline void DFS(int nod)
{
    int dim = L[nod] . size() , i;
    while(ind[nod] < dim)
    {
        i = L[nod][ind[nod]++];
        if(!viz[i])
        {
            viz[i] = true;
            DFS(X[i] + Y[i] - nod);
        }
    }
    ++k;
    sol[k] = nod;
}
int main()
{
    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);
    }
    if(!CHECK())
        fout << "-1\n";
    else
    {
        DFS(1);

        for(int i = 1 ; i < k ; i++)
            fout << sol[i] << " ";
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}