Cod sursa(job #2184104)

Utilizator zanugMatyas Gergely zanug Data 23 martie 2018 18:45:31
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#define pb push_back

using namespace std;

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

const int NLIM = 1e5+10;
const int MLIM = 5e5+10;

struct cucc
{
    int x, idx;
};

int n, m;
vector < cucc > graf[NLIM];
bool b[MLIM];

vector < int > er;
vector < int > st;
int nr;


bool eul()
{
    for(int i = 1; i <= n; ++i)
        if(graf[i].size() % 2 || graf[i].size() == 0)
            return false;
    return true;
}

void dfs(int cnod)
{
    for(int i = 0; i < graf[cnod].size(); ++i)
    {
        if(!b[graf[cnod][i].idx])
        {
            b[graf[cnod][i].idx] = true;
            st.pb(graf[cnod][i].x);

            dfs(graf[cnod][i].x);
        }
    }
    er.pb(st.back());
    st.pop_back();
    return;
}

int main()
{
    fin >> n >> m;///

    cucc x, y;
    for(int i = 1; i <= m; ++i)
    {
        fin >> x.x >> y.x;///
        x.idx = y.idx = i;

        graf[x.x].pb(y);
        graf[y.x].pb(x);
    }

    if(eul())
    {
        nr = 1;
        st.pb(1);//cout << 1;
        dfs(1);//cout << 2;

        while(st.size());
        {
            er.pb(st.back());
            st.pop_back();
        }

        for(int i = er.size()-2; i > 0; --i)
        {
            fout << er[i] << " ";///
        }
    }
    else
    {
        fout << -1;///
    }

    return 0;
}