Cod sursa(job #2184141)

Utilizator zanugMatyas Gergely zanug Data 23 martie 2018 19:17:43
Problema Ciclu Eulerian Scor 100
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;

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

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())
    {
        st.pb(1);

        while(st.size())
        {
            int cnod = st.back();

            if(graf[cnod].size())
            {
                cucc nnod = graf[cnod].back();
                graf[cnod].pop_back();

                if(!b[nnod.idx])
                {
                    b[nnod.idx] = true;
                    st.pb(nnod.x);
                }
            }
            else
            {
                st.pop_back();
                er.pb(cnod);
            }
        }

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

    return 0;
}